NAME

Games::Sudoku::PatternSolver::Generator - produces 9x9 Sudoku solution grids and 9x9 Sudoku puzzles

DESCRIPTION

This sub module uses the Games::Sudoku::PatternSolver's POM ability (Pattern Overlay Method) to build solution grids and enables Games::Sudoku::PatternSolver::CPLogic to provide some indication of rating with the generated puzzles.

You may supply a grid of your liking to begin with, but it really doesn't matter because it is the (always) random order in which cell values are tried to be removed that make the essential difference, not the grid at launching point.

All Sudoku returned from the builder are well-posed (have a unique solution) and reduced (removing any of the givens would lead to > 1 solution). The script generate.pl shows how to filter the stream and find the hidden perls in puzzles, that may otherwise breeze past undetected.

METHODS

• get_sudoku_builder()

  SudokuPuzzle objects are returned from an iterator: $sudokuBuilder = get_sudoku_builder($startGrid);

  A grid string (81 chars) can be either a completed solution to start from, or a puzzle to be checked for reducibility.

  while (my $sudoku = &$sudokuBuilder) { inspect and either reject or do something with $sudoku }

  1. solution - a string of 81 characters (default undef) The values in the string are given by numbers 1-9. Their positons must comply to Sudoku constraints, this will not be checked again. The start grid may already contain empty cells ('.', '0', or spaces) to give a higher likelihood to arriving at puzzles which exhibit a desired symmetry or certain pattern. If none is given (default) a new random solution is generated on each iteration and after the trials for random removal are depleted.

  2. givensMax - a number between 17 and 81 (default = 40) Because puzzles of interest are found to usually have 17 to 35 givens, and because the alternating process of removing/replacing random cells and solving is very time consuming, one should always drop a certain number of random positions at start to get to the promising depth fast. The vast majority of minimal Sudoku has 22 to 27 givens. But if the chosen outset is too low (< 35), the probability rises that almost all grids right after dropping them already have no unique solution and require a looong time of retrying. Meanwhile all other Sudoku of possible interest with just a bit more givens, that could have been detected and/or saved while drilling down, remain unnoticed.

The methods get_grid_builder() or generate_grids() can produce fully filled solutions at a high rate. These methods are using plain overlay of random patterns (POM) and not taking any shortcut as Latin Squares method does. Therefore the resulting grids all are guaranteed to conform to Sudoku rules and are spread absolutely randomly across the space of all Sudoku. Lest one should like to create puzzles with certain symmetries or patterns in position of givens, they are probably only of interest for bench marking.

EXPORTS

The module optionally exports get_sudoku_builder(), get_grid_builder() and provides the import tag ':all'.

AUTHOR

Steffen Heinrich, Jan. 2024

COPYRIGHT

The following copyright notice applies to all the files provided in this distribution, including binary files, unless explicitly noted otherwise.

Copyright 2024 Steffen Heinrich

SEE ALSO

https://www.sudokuwiki.org/Pattern_Overlay, https://sites.math.washington.edu/~morrow/mcm/team2280.pdf

LICENSE

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.