# NAME

Games::Sudoku::Solver - Solve 9x9-Sudokus recursively.

# VERSION

This document describes Games::Sudoku::Solver version 1.0.0

# SYNOPSIS

``````    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] );
}``````

# DESCRIPTION

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.

## Algorithm

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:

1. Build the list of free cells starting from the upper left corner. Set an index on the first free cell.

2. 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).

# SUBROUTINES/METHODS

There are two export tags. `Minimal` exports `sudoku_set`, `sudoku_solve`, and `sudoku_print`. `All` exports all subroutines described below.

## `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:  ---``````

## `sudoku_print`

``````      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``````

## `sudoku_set`

``````      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.``````

## `sudoku_solve`

``````  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:

Maximal number of solutions (0=unbound)
``    solution_max    => 10``
Unique digits on the 1. diagonal (upper-left to lower-right)
``````    diagonal_ul_lr  =>  0                       # not unique
diagonal_ul_lr  =>  1                       # unique``````
Unique digits on the 2. diagonal (lower-left to upper-right)
``````    diagonal_ll_ur  =>  0                       # not unique
diagonal_ll_ur  =>  1                       # unique``````

# DIAGNOSTICS

error `"\$0 : failed to open input file \$filename : \$!\n"`

Subroutine `sudoku_read` could not open the specified file.

error `"error in file '\$filename', line \${.}.\n"`

Subroutine `sudoku_read` found a format error when reading the specified file.

croak `"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`).

croak `"value repeated in column \${i} \n"`

Subroutine `sudoku_check` found a format error when checking a Sudoku (may be after reading it with `sudoku_read`).

croak `"value repeated in submatrix \${i} \n"`

Subroutine `sudoku_check` found a format error when checking a Sudoku (may be after reading it with `sudoku_read`).

warning `"\$0 : failed to close input file \$filename : \$!\n";`

Subroutine `sudoku_read` could not close the specified file.

# CONFIGURATION AND ENVIRONMENT

Games::Sudoku::Solver requires no configuration files or environment variables.

# DEPENDENCIES

``````    Carp  - warn of errors
Clone - recursively copy Perl datatypes``````

None reported.

# BUGS AND LIMITATIONS

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.

# AUTHOR

Dr.-Ing. Fritz Mehner `<mehner@fh-swf.de>`

Copyright (c) 2006-2007, Dr.-Ing. Fritz Mehner `<mehner@fh-swf.de>`. All rights reserved.