Games::Sudoku::Solver - Solve 9x9-Sudokus recursively.
This document describes Games::Sudoku::Solver version 1.0.0
use Games::Sudoku::Solver qw(:Minimal set_solution_max count_occupied_cells); # specify a Sudoku as flat array (this one has 10 solutions) my @sudoku_raw = qw( 0 4 0 0 2 0 9 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 6 8 5 0 5 8 2 3 0 0 7 0 0 0 0 0 8 0 7 0 0 0 0 0 9 0 0 5 1 3 8 0 9 7 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 4 0 3 0 0 0 0 ); my @sudoku; # the Sudoku data structure my @solution; # the solution data structure sudoku_set( \@sudoku, \@sudoku_raw ); # convert raw to internal representation print "\n===== Sudoku =====\n"; sudoku_print( \@sudoku ); # print the Sudoku my $cells_occupied = count_occupied_cells( \@sudoku ); # some statistics print "\n", $cells_occupied, " cells occupied, ", 81-$cells_occupied, " cells free\n"; set_solution_max(4); # stop having 4 solutions found my $solutions = sudoku_solve( \@sudoku, \@solution); # solve the Sudoku foreach my $n ( 1..$solutions ) { # print the solutions print "\n--- solution $n ---\n"; sudoku_print( $solution[$n-1] ); }
This module solves 9x9-Sudoku puzzles by recursion. There is no restriction to the difficulty and the number of solutions.
The puzzle can be stored in a single dimension array or in a file, where unknown cells are presented by zeros or points.
Solving Sudokus is perfectly suited for the application of a recursive algorithm. The basic idea: Find the first free cell, insert an allowed value and get a new Sudoku with one free cell less or a solution if it is complete. In more details:
Build the list of free cells starting from the upper left corner. Set an index on the first free cell.
Build the set of allowed (and until now unused) values for the actual cell by inspecting the according row, column and submatrix.
If there exists an allowed values and the Sudoku is complete a solution is found. Discard this value for this cell from the set of allowed values. Go to step 2.
If there exists an allowed values and the Sudoku is not complete go ahead to the next free cell in the list of free cells. Go to step 2.
If there exists no allowed value free the actual cell and go back one position in the list of free cells. Go to step 2.
The algorithm walks through a tree of mostly incomplete Sudokus. The leaves which are complete are solutions (if any).
There are two export tags. Minimal exports sudoku_set, sudoku_solve, and sudoku_print. All exports all subroutines described below.
Minimal
sudoku_set
sudoku_solve
sudoku_print
All
count_occupied_cells
PURPOSE: count actually occupied cells PARAMETERS: (1) reference to a Sudoku (array of arrays) RETURNS: number of occupied cells
get_solution_max
PURPOSE: get maximal number of solutions to search for PARAMETERS: --- RETURNS: maximal number of solutions to search for
set_solution_max
PURPOSE: set maximal number of solutions to search for PARAMETERS: postive number (postive sign allowed) RETURNS: ---
sudoku_check
PURPOSE: Check Sudoku for correctness DESCRIPTION: - check rows, columns - check submatrices; numbering: +---+---+---+ | 1 | 2 | 3 | +---+---+---+ | 4 | 5 | 6 | +---+---+---+ | 7 | 8 | 9 | +---+---+---+ Die of error (croak) if Sudoku is not correct. PARAMETERS: (1) reference to a Sudoku (array of arrays) RETURNS: ---
PURPOSE: print Sudoku DESCRIPTION: Simple text output PARAMETERS: (1) reference to a Sudoku (array of arrays) RETURNS: ---
sudoku_read
PURPOSE: read a Sudoku from a file; check format PARAMETERS: (1) reference to a Sudoku (array of arrays) (2) name of the input file (scalar) RETURNS: --- There a two file formats. Format 1 specifies empty cells with 0. The cells are separated by whitespaces. Perl comments are allowed on separate lines: # 1 solution 0 3 0 2 6 7 0 4 0 1 0 0 0 0 0 0 0 5 7 4 0 5 0 1 0 9 2 9 0 5 0 0 0 1 0 3 6 0 0 0 5 0 0 0 8 8 0 4 0 0 0 7 0 9 2 9 0 7 0 4 0 8 6 3 0 0 0 0 0 0 0 4 0 5 0 6 1 2 0 3 0 The second format uses points for the empty cells. Separating whitespaces are not allowed: # 1 solution 3.4...6.2 9..627..4 6..1.4..7 249...731 16.....85 .83...46. 7..8.5..3 ...263... 8.5...9.6 There is no restriction on the number of empty cells. A completely empty Sudokus would generate all possible solutions: # 6.670.903.752.021.072.936.960 solutions # 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
PURPOSE: store the 81 values of a Sudoku from a flat array into the internal representation (array of arrays) PARAMETERS: (1) reference to a Sudoku (array of arrays) (2) reference to flat array of 81 values (digits) RETURNS: --- COMMENTS: The Sudoku will be checked for correctness.
DESCRIPTION: solve a Sudoku by recursion PARAMETERS: (1) reference to a Sudoku (array of arrays) (2) reference to a solution array (array of arrays of arrays) (3) restrictions (hash; optional) RETURNS: number of solutions found
Possible restrictions are:
solution_max => 10
diagonal_ul_lr => 0 # not unique diagonal_ul_lr => 1 # unique
diagonal_ll_ur => 0 # not unique diagonal_ll_ur => 1 # unique
"$0 : failed to open input file $filename : $!\n"
Subroutine sudoku_read could not open the specified file.
"error in file '$filename', line ${.}.\n"
Subroutine sudoku_read found a format error when reading the specified file.
"value repeated in line ${i} \n"
Subroutine sudoku_check found a format error when checking a Sudoku (may be after reading it with sudoku_read).
"value repeated in column ${i} \n"
"value repeated in submatrix ${i} \n"
"$0 : failed to close input file $filename : $!\n";
Subroutine sudoku_read could not close the specified file.
Games::Sudoku::Solver requires no configuration files or environment variables.
Carp - warn of errors Clone - recursively copy Perl datatypes
None reported.
This module can only solve 9x9-Sudokus. No bugs have been reported.
Please report any bugs or feature requests to bug-games-sudoku-solver@rt.cpan.org, or through the web interface at http://rt.cpan.org.
bug-games-sudoku-solver@rt.cpan.org
Dr.-Ing. Fritz Mehner <mehner@fh-swf.de>
<mehner@fh-swf.de>
Copyright (c) 2006-2007, Dr.-Ing. Fritz Mehner <mehner@fh-swf.de>. All rights reserved.
This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself. See perlartistic.
BECAUSE THIS SOFTWARE IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE SOFTWARE, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE SOFTWARE "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE SOFTWARE IS WITH YOU. SHOULD THE SOFTWARE PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR CORRECTION.
IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE SOFTWARE AS PERMITTED BY THE ABOVE LICENCE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE SOFTWARE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE SOFTWARE TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
To install Games::Sudoku::Solver, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Games::Sudoku::Solver
CPAN shell
perl -MCPAN -e shell install Games::Sudoku::Solver
For more information on module installation, please visit the detailed CPAN module installation guide.