NAME

Games::Sudoku::General - Solve sudoku-like puzzles.

SYNOPSIS

$su = Games::Sudoku::General->new ();
print $su->problem(<<eod)->solution();
3 . . . . 8 . 2 .
. . . . . 9 . . .
. . 2 7 . 5 . . .
2 4 . 5 . . 8 . .
. 8 5 . 7 4 . . 6
. 3 . . . . 9 4 .
1 . 4 . . . . 7 2
. . 6 9 . . . 5 .
. 7 . 6 1 2 . . 9
eod

DESCRIPTION

This package solves puzzles that involve the allocation of symbols among a number of sets, such that no set contains more than one of any symbol. This class of problem includes the puzzles known as 'Sudoku', 'Number Place', and 'Wasabi'.

Each Sudoku puzzle is considered to be made up of a number of cells, each of which is a member of one or more sets, and each of which may contain exactly one symbol. The contents of some of the cells are given, and the problem is to deduce the contents of the rest of the cells.

Although such puzzles as Sudoku are presented on a square grid, this package does not assume any particular geometry. Instead, the topology of the puzzle is defined by the user in terms of a list of the sets to which each cell belongs. Some topology generators are provided, but the user has the option of hand-specifying an arbitrary topology.

Even on the standard 9 x 9 Sudoku topology there are variants in which unspecified cells are constrained in various ways (odd/even, high/low). Such variants are accomodated by defining named sets of allowed symbols, and then giving the set name for each unoccupied cell to which it applies. See allowed_symbols for more information and an example.

This module is able not only to solve a variety of Sudoku-like puzzles, but to 'explain' how it arrived at its solution. The steps() method, called after a solution is generated, lists in order what solution constraints were applied, what cell each constraint is applied to, and what symbol the cell was constrained to.

Test script t/sudoku.t demonstrates these features. ActivePerl users will have to download the kit from http://www.cpan.org/ or http://search.cpan.org/~wyant/ to get this file.

Exported symbols

No symbols are exported by default, but the following things are available for export:

Status values exported by the :status tag
  SUDOKU_SUCCESS
    This means what you think it does.
  SUDOKU_NO_SOLUTION
    This means the method exhausted all possible
    soltions without finding one
  SUDOKU_TOO_HARD
    This means the iteration_limit attribute was
    set to a positive number and the solution()
    method hit the limit without finding a solution.

The :all tag is provided for convenience, but it exports the same symbols as :status.

Attributes

Games::Sudoku::General objects have the following attributes, which may normally be accessed by the get() method, and changed by the set() method.

In parentheses after the name of the attribute is the word "number" or "string", giving the data type of the attribute. The parentheses may also contain the words "read-only" to denote a read-only attribute or "write-only" to denote a write-only attribute.

In general, the write-only attributes exist as a convenience to the user, and provide a shorthand way to set a cluster of attributes at the same time. At the moment all of them are concerned with generating problem topologies, which are a real pain to specify by hand.

allowed_symbols (string)

This attribute names and defines sets of allowed symbols which may appear in empty cells. The set definitions are whitespace-delimited and each consists of a string of the form 'name=symbol,symbol...' where the 'name' is the name of the set, and the symbols are a list of the symbols valid in a cell to which that set applies.

For example, if you have an odd/even puzzle (i.e. you are given that at least some of the unoccupied cells are even or odd but not both), you might want to

$su->set (allowed_symbols => <<eod);
o=1,3,5,7,9
e=2,4,6,8
eod

and then define the problem like this:

$su->problem (<<eod);
1 o e o e e o e 3
o o e o 6 e o o e
e e 3 o o 1 o e e
e 7 o 1 o e e o e
o e 8 e e o 5 o o
o e o o e 3 e 4 o
e o o 8 o o 6 o e
o o o e 1 e e e o
6 e e e o o o o 7
eod

To eliminate an individual allowed symbol set, set it to an empty string (e.g. $su->set (allowed_symbols => 'o=');). To eliminate all symbol sets, set the entire attribute to the empty string.

Allowed symbol set names may not conflict with symbol names. If you set the symbol attribute, all allowed symbol sets are deleted, because that seemed to be the most expeditious way to enforce this restriction across a symbol set change.

Because symbol set names must be parsed like symbol names when a problem is defined, they also affect the need for whitespace on problem input. See the problem() documentation for full details.

brick (string, write-only)

This "virtual" attribute is a convenience, which causes the object to be configured with a topology of rows, columns, and rectangles. The value set must be either a comma-separated list of three numbers (e.g. '3,2,6') or a reference to a list containing three numbers (e.g. [3, 2, 6]). Either way, the numbers represent the horizontal dimension of the rectangle (in columns), the vertical dimension of the rectangle (in rows), and the overall size of the puzzle square. For example,

$su->set (brick => [3, 2, 6])

generates a topology that looks like this

+-------+-------+
| x x x | x x x |
| x x x | x x x |
+-------+-------+
| x x x | x x x |
| x x x | x x x |
+-------+-------+
| x x x | x x x |
| x x x | x x x |
+-------+-------+

The overall size of the puzzle must be a multiple of both the horizontal and vertical rectangle size.

Setting this modifies the following "real" attributes:

columns is set to the size of the big square;
symbols is set to "." and the numbers "1", "2",
  and so on, up to the size of the big square;
topology is set to represent the rows,  columns,
  and small squares in the big square, with row
  sets named "r0", "r1", and so on, column sets
  named "c0", "c1", and so on, and small
  rectangle sets named "s0", "s1", and so on for
  historical reasons.

columns (number)

This attribute defines the number of columns of data to be used when formatting the topology attribute, or the solution to a puzzle.

corresponding (number, write-only)

This "virtual" attribute is a convenience, which causes the object to be configured for "corresponding-cell" Sudoku. The topology is the same as 'set sudoku', but in addition corresponding cells in the small squares must have different values. The extra set names are "u0", "u1", and so on.

This kind of puzzle is also called "disjoint groups."

cube (string, write-only)

This "virtual" attribute is a convenience, which causes the object to be configured for cubical sudoku. The string takes one of the following values:

* 'full' generates a topology that includes all faces of the cube. The sets are the faces of the cube, and the rows, columns, and (for lack of a better word) planes of cells that circle the cube.

To enter the problem, imagine the cube unfolded to make a Latin cross. Then, enter the problem in order by faces, rows, and columns, top to bottom and left to right. The order of entry is actually in order by cell number, as given below.

              +-------------+
              |  0  1  2  3 |
              |  4  5  6  7 |
              |  8  9 10 11 |
              | 12 13 14 15 |
+-------------+-------------+-------------+
| 16 17 18 19 | 32 33 34 35 | 48 49 50 51 |
| 20 21 22 23 | 36 37 38 39 | 52 53 54 55 |
| 24 25 26 27 | 40 41 42 43 | 56 57 58 59 |
| 28 29 30 31 | 44 45 46 47 | 60 61 62 63 |
+-------------+-------------+-------------+
              | 64 65 66 67 |
              | 68 69 70 71 |
              | 72 73 74 75 |
              | 76 77 78 79 |
              +-------------+
              | 80 81 82 83 |
              | 84 85 86 87 |
              | 88 89 90 91 |
              | 92 93 94 95 |
              +-------------+

The solution will be displayed in order by cell number, with line breaks controlled by the columns attribute, just like any other solution presented by this package.

I have seen such puzzles presented with the bottom square placed to the right and rotated counterclockwise 90 degrees. You will need to perform the opposite rotation when you enter the problem.

* 'half' generates a topology that looks like an isometric view of a cube, with the puzzle on the visible faces. The faces are divided in half, since the set size here is 8, not 16. Imagine the isometric unfolded to make an L-shape. Then, enter the problem in order by faces, rows, and columns, top to bottom and left to right. The order of entry is actually in order by cell number, as given below.

+-------------------+
|  0    1    2    3 |
|                   |
|  4    5    6    7 |
+-------------------+
|  8    9   10   11 |
|                   |
| 12   13   14   15 |
+---------+---------+-------------------+
| 16   17 | 18   19 | 32   33   34   35 |
|         |         |                   |
| 20   21 | 22   23 | 36   37   38   39 |
|         |         +-------------------+
| 24   25 | 26   27 | 40   41   42   43 |
|         |         |                   |
| 28   29 | 30   31 | 44   45   46   47 |
+---------+---------+-------------------+

The solution will be displayed in order by cell number, with line breaks controlled by the columns attribute, just like any other solution presented by this package.

For all the 'cube' puzzles, the "columns" attribute is set to 4, and the symbols attribute to the numbers 1 to the size of the largest set (16 for the full cube, 8 for the half or isometric cube). I have seen full cube puzzles done with hex digits 0 to F; these are handled most easily by setting the symbols attribute appropriately:

$su->set (cube => 'full', symbols => <<eod);
. 0 1 2 3 4 5 6 7 8 9 A B C D E F
eod

debug (number)

This attribute, if not 0, causes debugging information to be displayed. Values other than 0 are not supported, in the sense that the author makes no commitment what will happen when a non-zero value is set, and further reserves the right to change this behaviour without notice of any sort, and without documenting the changes.

iteration_limit (number)

This attribute governs how hard the solution() method tries to solve a problem. An iteration is an attempt to use the backtrack constraint. Since what this really counts is the number of times we place a backtrack constraint on the stack, not the number of values generated from that constraint, I suspect 10 to 20 is reasonable for a "normal" sudoku problem.

The default is 0, which imposes no limit.

largest_set (number, read-only)

This read-only attribute returns the size of the largest set defined by the current topology.

latin (number, write-only)

This "virtual" attribute is a convenience, which causes the object to be configured to handle a Latin square. The value gives the size of the square. Setting this modifies the following "real" attributes:

columns is set to the size of the square;
symbols is set to "." and the letters "A", "B",
  and so on, up to the size of the square;
topology is set to represent the rows and columns
  of a square, with row sets named "r0", "r1",
  and so on, and the column sets named "c0",
  "c1", and so on.

max_tuple (number)

This attribute represents the maximum-sized tuple to consider for the tuple constraint. It is possible that one might want to modify this upward for large puzzles, or downward for small ones.

The default is 4, meaning that the solution considers doubles, triples, and quads only.

name (string)

This attribute is for information, and is not used by the class.

output_delimiter (string)

This attribute specifies the delimiter to be used between cell values on output. The default is a single space.

status_text (text, read-only)

This attribute is a short piece of text corresponding to the status_value.

status_value (number)

The solution() method sets a status, which can be retrieved via this attribute. The retrieved value is one of

SUDOKU_SUCCESS
  This means what you think it does.
SUDOKU_NO_SOLUTION
  This means the method exhausted all possible
  soltions without finding one
SUDOKU_TOO_HARD
  This means the iteration_limit attribute was
  set to a positive number and the solution()
  method hit the limit without finding a solution.

sudoku (number, write-only)

This attribute is a convenience, which causes the object to be configured to handle a standard Sudoku square. The value gives the size of the small squares into which the big square is divided. The big square's side is the square of the value.

For example, the customary Sudoku topology is set by

$su->set (sudoku => 3);

This attribute is implemented in terms of 'set brick', and modifies the same "real" attributes. See brick for the details.

sudokux (number, write-only)

This attribute is a convenience. It is similar to the 'sudoku' attribute, but the topology includes both main diagonals (set names 'd0' and 'd1') in addition to the standard sets. See brick for the details, since that's ultimately how this attribute is implemented.

symbols (string)

This attribute defines the symbols to be used in the puzzle. Any printing characters may be used except ",". Multi-character symbols are supported. The value of the attribute is a whitespace-delimited list of the symbols, though the whitespace is optional if all symbols (and symbol constraints if any) are a single character. See the problem() documentation for full details.

The first symbol in the list is the one that represents an empty cell. Except for this, the order of the symbols is immaterial.

The symbols defined here are used only for input or output. It is perfectly legitimate to set symbols, call the problem() method, and then change the symbols. The solution() method will return solutions in the new symbol set. I have no idea why you would want to do this.

topology (string)

This attribute defines the topology of the puzzle, in terms of what sets each cell belongs to. Each cell is defined in terms of a comma-delimited list of the names of the sets it belongs to, and the string is a whitespace-delimited list of cell definitions. For example, a three-by-three grid with diagonals can be defined as follows in terms of sets r1, r2, and r3 for the rows, c1, c2, and c3 for the columns, and d1 and d2 for the diagonals:

r1,c1,d1 r1,c2       r1,c3,d2
r2,c1    r2,c2,d1,d2 r2,c3
r3,c1,d1 r3,c2       r3,c3,d2

The parser treats line breaks as whitespace. That is to say, the above definition would be the same if it were all on one line.

You do not need to define the sets themselves anywhere. The package defines each set as it encounters it in the topology definition.

Setting the topology invalidates any currently-set-up problem.

Methods

This package provides the following public methods:

$su = Games::Sudoku::General->new ()

This method instantiates a new Games::Sudoku::General object. Any arguments are passed to the set() method. If, after processing the arguments, the object does not have a topology,

$self->set (sudoku => 3)

is called. If there is no symbols setting (which could happen if the user passed an explicit topology),

$self->set (symbols => join ' ', '.',
  1 .. $self->get ('largest_set'))

is called. If, after all this, there is still no columns setting, the number of columns is set to the number of symbols, excluding the "empty cell" symbol.

The newly-instantiated object is returned.

$su->add_set ($name => $cell ...)

This method adds to the current topology a new set with the given name, and consisting of the given cells. The set name must not already exist, but the cells must already exist. In other words, you can't modify an existing set with this method, nor can you add new cells.

%constraints_used = $su->constraints_used;

This method returns a hash containing the constraints used in the most recent call to solution(), and the number of times each was used. The constraint codes are the same as for the steps() method. If called in scalar context it returns a string representing the constraints used at least once, in canonical order (i.e. in the order documented in the steps() method).

Note: As of version 0.002, the string returned by the scalar has spaces delimiting the constraint names. They were not delimited in version 0.001

$value = $su->get ($name);

This method returns the value of the named attribute. An exception is thrown if the given name does not correspond to an attribute that can be read. That is, the given name must appear on the list of attributes above, and not be marked "write-only".

If called in list context, you can pass multiple attribute names, and get back a list of their values. If called in scalar context, attribute names after the first are ignored.

$su->problem ($string);

This method specifies the problem to be solved, and sets the object up to solve the problem.

The problem is specified by a whitespace-delimited list of the symbols contained by each cell. You can format the puzzle definition into a square grid (e.g. the SYNOPSIS section), but to the parser a line break is no different than spaces. If you pass an empty string, an empty problem will be set up - that is, one in which all cells are empty.

An exception will be thrown if:

* The puzzle definition uses an unknown symbol;
* The puzzle definition has a different number
  of cells from the topology definition;
* There exists a set with more members than the
  number of symbols, excluding the "empty"
  symbol.

The whitespace delimiter is optional, provided that all symbol names are exactly one character long, and that you have not defined any symbol constraint names more than one character long since the last time you set the symbol names.

$su->set ($name => $value);

This method sets the value of the named attribute. An exception is thrown if the given name does not correspond to an attribute that can be written. That is, the given name must appear on the list of attributes above, and not be marked "read-only". An exception is also thrown if the value is invalid, e.g. a non-numeric value for an attribute marked "number".

You can pass multiple name-value pairs. If an exception is thrown, all settings before the exception will be made, and all settings after the exception will not be made.

The object itself is returned.

$string = $su->solution ();

This method returns the next solution to the problem, or undef if there are no further solutions. The solution is a blank-delimited list of the symbols each cell contains, with line breaks as specified by the 'columns' attribute. If the problem() method has not been called, an exception is thrown.

Status values set:

SUDOKU_SUCCESS
SUDOKU_NO_SOLUTION
SUDOKU_TOO_HARD

$string = $su->steps ();

This method returns the steps taken to solve the problem. If no solution was found, it returns the steps taken to determine this. If called in list context, you get an actual copy of the list. The first element is the name of the constraint applied:

F = forced: only one value works in this cell;
N = numeration or necessary: this is the only cell
    that can supply the given value;
B = box claim: if a candidate number appears in only
    one row or column of a given box, it can be
    eliminated as a candidate in that row or column
    but outside that box;
T = tuple, which is a generalization of the concept
    pair, triple, and so on. These come in two
    varieties for a given size of the tuple N:
  naked: N cells contain among them N values, so
    no cells outside the tuple can supply those
    values.
  hidden: N cells contain N values which do not
    occur outside those cells, so any other values
    in the tuple are supressed.
? = no constraint: generated in backtrack mode.

See http://www.research.att.com/~gsf/sudoku/ and http://www.angusj.com/sudoku/hints.php for fuller definitions of the constraints and how they are applied.

The second value is the cell number, as defined by the topology setting. For the 'sudoku' and 'latin' settings, the cells are numbered from zero, row-by-row. If you did your own topology, the first cell you defined is 0, the second is 1, and so on.

The third value is the value assigned to the cell. If returned in list context, it is the number assigned to the cell's symbol. If in scalar context, it is the symbol itself.

EXECUTABLES

The distribution for this module also contains the script 'sudokug', which is a command-driven interface to this module.

BUGS

The X, Y, and W constraints (to use Glenn Fowler's terminology) are not yet handled. The package can solve puzzles that need these constraints, but it does so by backtracking.

Please report bugs either through http://rt.cpan.org/ or by mail to the author.

ACKNOWLEDGMENTS

The authow would like to acknowledge the following, without whom this module would not exist:

Glenn Fowler of AT&T, whose http://www.research.att.com/~gsf/sudoku/ provided the methodological starting point and basic terminology, whose 'sudoku' executable provided a reference implementation for checking the solutions of standard Sudoku puzzles, and whose constraint taxonomy data set provided invaluable test data.

Angus Johnson, whose fulsome explanation at http://www.angusj.com/sudoku/hints.php was a great help in understanding the mechanics of solving Sudoku puzzles.

Ed Pegg, Jr, whose Mathematical Association of America Math Games column for September 5 2005 (http://www.maa.org/editorial/mathgames/mathgames_09_05_05.html) provided a treasure trove of 'non-standard' Sudoku puzzles.

MODIFICATIONS

0.001 T. R. Wyant
  Initial release to CPAN.
0.002 T. R. Wyant
  Format solution nicely for multi-character symbols.
  Fixed error in values eliminated by a hidden tuple.
  Recoded 'set sudokug' in terms of 'set brick', thus
    fixing an error in generating the small squares.
  Added method add_set(), and recoded 'set sudokux' in
    terms of this and 'set sudokug', thus fixing the
    same error that 'set sudoku' had.
  Put spaces in the result of scalar constraints_used.
  Spiffed up the POD.
0.003 T. R. Wyant
  Added 'set corresponding' and 'set max_tuple'.
  Added cubic sudoku (via 'set cube').
  Fixed horrendous inefficiency in backtrack logic.

SEE ALSO

The Games-Sudoku package by Eugene Kulesha (see http://search.cpan.org/~jset/) solves the standard 9x9 version of the puzzle.

The Games-Sudoku-OO package by Michael Cope (see http://search.cpan.org/~cope/) also solves the standard 9x9 version of the puzzle, with an option to solve (to the extent possible) a single row, column, or square. The implementation may be extensable to other topologies than the standard one.

The Games-YASudoku package by Andrew Wyllie (see http://search.cpan.org/~wyllie/) also solves the standard 9x9 version of the puzzle. In contrast to the other packages, this one represents the board as a list of cell/value pairs.

AUTHOR

Thomas R. Wyant, III (wyant at cpan dot org)

COPYRIGHT

Copyright 2005 by Thomas R. Wyant, III (wyant at cpan dot org). All rights reserved.

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

cpanm Games::Sudoku::General

perl -MCPAN -e shell
install Games::Sudoku::General