The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.
 / 
Games-Sudoku-PatternSolver-0.07
River stage zero No dependents
/ Games::Sudoku::PatternSolver

NAME

Games::Sudoku::PatternSolver - Solve and generate Sudoku 9x9 puzzles.

DESCRIPTION

A Sudoku solver and generator. It works by application of the pattern overlay method (POM) in a backtracking process.

Note: For this module the term 'pattern' refers to a 9x9 matrix, holding the final 9 positions of any single symbol.

SYNOPSIS

  use Games::Sudoku::PatternSolver qw( solve );

  $result = solve( '.2.4.6.8....2......9......1..4......51.....9.....4.5.335..6....9...823.5..1.....8' );
  print_grid( $result->{solutions}[0] );

  use Games::Sudoku::PatternSolver::Generator qw(get_grid_builder get_sudoku_builder);

  $grid_builder = get_grid_builder();
  $solution = &$grid_builder( $do_shuffle );

  $generator = get_sudoku_builder( $solution );
  $sudokuHash = &$generator();
  print $sudokuHash->{strPuzzle}, "\n";

MODULES AND UTILITIES

PatternSolver

Can solve any valid standard 9x9 puzzle.

It is notable in that it tries to find a combination of 9 out of 46656 unique patterns in which a number may be placed on the grid. If a faulty puzzle has very many solutions and the $MAX_SOLUTIONS switch is false, the solver can find them all, given sufficient time and computer memory.

solve( <puzzle> )

The input can be an 81-character string with zeroes or non-digits for empty cells, it can be 81 individual values, an arrayref with these or a 9x9 AoA.

The return value is an unblessed hash reference, populated with properties of the puzzle and the results of the solving process:

strPuzzle
givensCount
uniqueGivens

Describing the puzzle.

seconds

Time needed for the entire solving process.

solutionCount

Normally == '1'. Is subject to $MAX_SOLUTIONS and the nature of the puzzle.

solutions

An arrayref with string representation of the one or more solutions.

logicSolved

Boolean, telling whether the limited power from PatternSolver::CPLogic sufficed for completion.

logicFilled

Number of cells filled by naked/hidden singles.

candidatesDropped

Number of individual candidates dropped from any cells without a value yet.

Especially the last couple of attributes can be taken for a rough estimation towards the puzzle's difficulty.

If logicSolved is false, it takes more than finding all naked or hidden pairs, triples or quads and all occasions for pointing and claiming. Hence we may put it at 'Master' level. (Maybe, a single xy-wing has forced our resorting to backtracking, but thats highly unlikely.) The majority of all chance created puzzles falls into this category. And many of these are insanely hard.

Otherwise, if candidatesDropped == 0, it means that the puzzle was solved with all values forced as naked or hidden singles. These can be called 'Easy' puzzles, more or less. But sometimes even singles are a bit difficult to spot.

And I personally prefer to play the grade in-between, and therefore call it the 'Advanced' level, not the 'Still relatively easy' level. Knowing for sure that nothing but spotting locked sets and applying locked candidates is required for victory, I find highly motivating.

Exports

PatternSolver optionally exports the symbols solve(), print_solution(), print_grid(), $VERBOSE, $MAX_SOLUTIONS, $LOOSE_MODE, $USE_LOGIC and provides the import tag ':all'.

The two helper functions give formatted output of selected attributes to STDOUT.

$VERBOSE (default false)

Give informative output.

$MAX_SOLUTIONS (default 2)

On (invalid) multi-solution puzzles, stop and return after this number of solutions is reached. Without a value (false) an exhaustive search is carried out.

$LOOSE_MODE (default true)

If true, puzzles with less than 8 different clues may get solved and can be generated by Games::Sudoku::PatternSolver::Generator. Does refuse to solve puzzles with less than 8 different clues if false. Knowledge of the different interpretations of Sudoku solution uniqueness is helpful for comprehension.

$USE_LOGIC (default true)

Load and apply the constraint logic from PatternSolver::CPLogic.

PatternSolver::CPLogic

 $USE_LOGIC = 1 (default)

Trying to fill in more values before the brute force gets unleashed comes with two advantages. It may significantly speed up the subsequent process of backtracking or even eleminate the need for it, because much less combinations have to be tried (or even none at all if the sudoku was solved), and it is also giving a few hints towards the puzzle's difficulty.

This helper module implements just the first and basic most strategies known to every occasional player. The 'hidden singles' and 'naked singles' directly force a value into a specific cell. And the just slightly more sophisticated 'locked sets' and 'locked candidates' rule out certain values in some cells. Because of the vast gain in speed (on average) switching off the logic is only reasonable for bechmarking the unamended pattern matching algorithm.

PatternSolver::Generator

Games::Sudoku::PatternSolver::Generator creates Sudoku puzzles with random properties. Apart from using the Games::Sudoku::PatternSolver there is nothing making this special.

As almost always when creating Sudokus programmatically, it follows the procedure

  1. start with any valid solution (a rule-compliant 9x9 grid with all 81 numbers)
  2. remove values in a random order (or copy them to a new blank grid) until a grid with a unique solution is found that cannot further be reduced

Puzzles returned are minimal and with respect to $LOOSE_MODE, have a unique solution (see below). The results are totally random, the majority being too hard for the average player and it is up to you, to filter them as you please. One would usually just call the sub reference returned from get_sudoku_builder() inside a loop to inspect and keep or skip the puzzles based upon their properties.

A solution (complete grid) can be fed to get_sudoku_builder(<strPuzzle>) as a common starting point. It is amazing to see how many very different puzzles can be produced from a single solution. (But of course they will all share this single solution.)

Absolutely random solution grids may be produced from a sub returned by get_grid_builder(). A boolean parameter <shuffle> passed to this sub, determines if the first row in the grids produced will always be 1 .. 9. (But is not minlexed!)

Play Sudoku

With Games::Sudoku::Html installed, the generated puzzles can get written to a single html page and selectively played in a web browser.

  use Games::Sudoku::Html qw( sudoku_html_page );
  @list = ( [$sudokuHash->{strPuzzle}, "<descriptive text with properties, rating, source, etc.>"], ... )
  $htmlpage = sudoku_html_page( \@list )

Or directly evoked from the command line:

  sudogen -C50 -GE | sudoku2html -o my_50_easy_sudoku.html

Generates one Page with 50 Sudoku of grade E(asy).

With Games::Sudoku::Pdf installed, the generated puzzles can be easily exported to pdf files:

  sudogen -C50 -GE | sudoku2pdf -o my_50_easy_sudoku.pdf

PatternSolver::Patterns

Internal module to access the serialized patterns. The method init_patterns() could be used to re-create the file with the 46656 binary symbol distribution patterns.

Scripts

Solution uniqueness

Quite a number of online discussions broach the issue of solution uniqueness; whether any valid puzzle really must have only one solution and whether a solving strategy is allowed to draw from the knowledge that only one solution can exist. On the other hand, no one seems to care or even be aware that the conventional nonchalant definition of the playing rules poses a slight deviance from the mathematical model of the problem at hand.

It is commonly felt that a new puzzle cannot be created from another one just by swapping numbers. But interestingly this insight never seems to get applied to the puzzle solutions.

Sudoku rules for novice players mandate that numbers 1 to 9 are to be put into the free cells and that one never should have to guess which number that might be. Consequently any puzzle with less than 8 unique givens is regarded as 'invalid', as it cannot doubtlessly be solved. Most Sudoku programs (solvers and generators alike) are implemented in accordance with this point of view.

Yet, if Sudoku is seen and explored as a general mathematical problem, the choice of symbols becomes irrelevant. The sole task is to determine the 9 sets of 9 cells that form the specific pattern or 'path' which complies with the constraints. The way these patterns get noted or marked forms no intrinsic part of the problem; nor has there to be a predefined, fix set of numbers, letters, colors or icons.

This viewpoint is allowing puzzles with less than 8 different givens and still only one solution to be regarded as valid. Some puzzles with only 5 different givens have indeed been found, but a mathematical proof for that being the minimum does not yet exist.

A readily solvable example: (After putting in the given symbols, the remaining 18 fields can be filled with absent numbers 6 and 9 or any other two symbols in just one possible way.)

  -------------------------
  | . . . | . 7 . | 4 . 5 |
  | 2 . 8 | . . . | . . 3 |
  | . . 3 | . 2 . | 8 . . |
  -------------------------
  | . . 2 | . . 1 | . . . |
  | . 8 . | . . . | . 1 . |
  | . . 5 | . . 2 | . 8 . |
  -------------------------
  | . . . | . . . | 7 . . |
  | . . . | 8 5 . | 3 4 2 |
  | . . . | 7 . 4 | . . . |
  -------------------------

With the default setting $LOOSE_MODE=1 PatternSolver and Generator can solve and generate such puzzles. (Though generating puzzles with less than 7 different givens will take quite some time and even more luck.)

DEPENDENCIES

COPYRIGHT AND LICENSE

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

This software is copyright (c) 2024 by Steffen Heinrich

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

SEE ALSO

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