NAME
Games::Sudoku::PatternSolver - Solve, generate and play Sudoku 9x9 grids.
DESCRIPTION
A Sudoku solver and generator. It works by application of the pattern overlay method (POM) in a backtracking process.
Lists of generated puzzles may get exported to html and can be played in a browser.
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();
use Games::Sudoku::PatternSolver::PlayerIF qw( sudoku_html_page );
@list = ( [$sudokuHash->{strPuzzle}, "<descriptive text with properties, rating, source, etc.>"], ... )
$htmlpage = sudoku_html_page( \@list )MODULES AND UTILITIES
PatternSolver
Games::Sudoku::PatternSolver can solve any standard 9x9 puzzle.
It is unique 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. And if a faulty puzzle has very many solutions the solver will find them all, given sufficient time and computer memory and $MAX_SOLUTIONS = false.
PatternSolver::CPLogic
$USE_LOGIC = 1 (default)A helper module with the two most basic strategies 'hidden singles' and 'naked singles' before solver begins backtracking. The aim is to fill some fields, thus reducing the number of patterns to try and consequently the time needed in total.
Switching it off would only make sense for debugging or bechmarking the unamended pattern matching algorithm, and without it there are not any clues available for a difficulty rating.
ToDo: With an additional implementation of the 'locked candidates' strategy, the rating's significance could probably get improved.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 (see "Ratings").
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!)
PatternSolver::PlayerIF
sudoku_html_page( arrayref ) returns a scalar html page, playable in a browserIts parameter is an array of arrays, each entry consisting of 2 items: a 81 character puzzle string and any descriptive text for the list entry. You may put as many puzzles as you like into the array, they can all be played from the one, javascript-driven static page.
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
solve_example.pl
Use of
Games::Sudoku::PatternSolver::solve()>.play_example.pl
Use of
Games::Sudoku::PatternSolver::Generator::get_sudoku_builder()> to create Sudoku lists and how to export them to playable html pages.
Some aspects of Sudoku
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.)
Ratings
The only sensible way to produce a Sudoku difficulty rating is by use of a 'human' solver. Either a real life person, be it a Sudoku hotshot or you yourself. Next best equipment is a solving program that implements exactly the human solving strategies, sorted by their assumed obviousness. Then during a programmatical solving process, the 'highest hill to climb' will determine the puzzles overall rating.
There are numerous Sudoku libraries written to that point, but PatternSolver is not one of them. With $USE_LOGIC=1, the only two implemented, very simple strategies (naked/hidden singles) get applied before the backtracking is even started. Alas, no 'rating' based on the resulting values provided for givensCount, uniqueGivens, cheatSolved, cheatFilled can possibly be very meaningful. But it may still be more realistic than the count of empty cells alone, which most online generators seem to use for their grading.
Brute force / Backtracking / Trial and error
Sudoku backtracking technique is not confined to solving a puzzle with a computer program. Many frequent paper and pencil players resort to backtracking when at their wit's end. And accordingly, with performance on mind, some of the better backtracking programs were implemented to first branch on cells with the lowest number of candidates.
Again, PatternSolver isn't one of these. :( Instead of looping over the cells of the puzzle grid, examining their values and properties, it rather uses an approach of fitting patterns with each other and with the givens. Nevertheless it still is a backtracking procedure.
Speed
Despite the effectively parallel backtracking algorithm Games::Sudoku::PatternSolver is not very fast. On a 3.3GHz Intel© Xeon© CPU desktop pc with 4 cores it takes ~0.5 seconds on average for each of the puzzles in HardestDatabase110626.txt. (http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539.html) E.g. Games::Sudoku::Kubedoku with a different approach to parallelization is about twice as fast on these. And the fastest solvers are playing in an entirely different league: https://codegolf.stackexchange.com/questions/190727/the-fastest-sudoku-solver
Depending on parameters, the generation of a new puzzle is taking around 1 second (where the new solution grids are being produced within 0.005 seconds).
DEPENDENCIES
COPYRIGHT
The following copyright notice applies to all the files provided in this distribution, including binary files, unless explicitly noted otherwise.
Copyright 2023 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.