Tom Wyant
and 1 contributors

# 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 accommodated by defining named sets of allowed symbols, and then giving the set name for each unoccupied cell to which it applies. See the `allowed_symbols` attribute 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 https://metacpan.org/release/Games-Sudoku-General 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 "boolean", "number" or "string", giving the data type of the attribute. Booleans are interpreted in the Perl sense: undef, 0, and '' are false, and anything else is true. 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.

autocopy (boolean)

If true, this attribute causes the generate() method to implicitly call copy() to copy the generated problem to the clipboard.

This attribute is false by default.

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 two numbers (e.g. '3,2') or a reference to a list containing two numbers (e.g. [3, 2]). Either way, the numbers represent the horizontal dimension of the rectangle (in columns) and the vertical dimension of the rectangle (in rows). The overall size of the puzzle square is the product of these. For example,

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

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

Originally there was a third argument giving the total size of the puzzle. Beginning with version 0.006 this was deprecated, since it appeared to me to be redundant. As of version 0.021, all uses of this argument resulted in a warning. As of version 0.022, use of the third argument will become fatal.

Setting this attribute 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 rectangles 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 present in a line of output 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 is either a number, or 'full', or 'half'.

* a number sets the topology to a Dion cube of the given order. That is,

`` sudokug> set cube 3``

generates a 9 x 9 x 9 Dion cube, with the small squares being 3 x 3. The problem is entered in plane, row, and column order, as though you were entering the required number of normal Sudoku puzzles back-to-back.

* '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 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 the 'full' and 'half' 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 behavior without notice of any sort, and without documenting the changes.

generation_limit (number)

This attribute governs how hard the generate() method tries to generate a problem. If generate() cannot generate a problem after this number of tries, it gives up.

The default is 30.

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.

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.

null (string, write-only)

This "virtual" attribute is a convenience, which causes the object to be configured with the given number of cells, but no topology. The topology must be added later using the add_set method once for each set of cells to be created.

The value must be either a comma-separated list of one to three numbers (e.g. '81,9,9') or a reference to a list containing one to three numbers (e.g. [81, 9, 9]). The first (and only required) number gives the number of cells. The second, if supplied, sets the 'columns' attribute, and the third, if supplied, sets the 'rows' attribute. For example,

`````` \$su->set (null => [36, 6]);
\$su->add_set (r0 => 0, 1, 2, 3, 4, 5);
\$su->add_set (r1 => 6, 7, 8, 9, 10, 11);
...
\$su->add_set (c0 => 0, 6, 12, 18, 24, 30);
\$su->add_set (c1 => 1, 7, 13, 19, 25, 31);
...
\$su->add_set (s0 => 0, 1, 2, 6, 7, 8);
\$su->add_set (s1 => 3, 4, 5, 9, 10, 11);
...``````

Generates the topology equivalent to

`` \$su->set (brick => [3, 2])``
output_delimiter (string)

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

quincunx (text, write-only)

This "virtual" attribute is a convenience, which causes the object to be configured as a quincunx (a. k. a. 'Samurai Sudoku' at http://www.samurai-sudoku.com/). The value must be either a comma-separated list of one to two numbers (e.g. '3,1') or a reference to a list of one to two numbers (e.g. [3, 1]). In either case, the numbers are the order of the quincunx (3 corresponding to the usual 'Samurai Sudoku' configuration), and the gap between the arms of the quincunx, in small squares. The gap must be strictly less than the order, and the same parity (odd or even) as the order. If the gap is not specified, it defaults to the smallest possible.

To be specific,

`` \$su->set(quincunx => 3)``

is equivalent to

`` \$su->set(quincunx => [3, 1])``

and both specify the 'Samurai Sudoku' configuration.

The actual topology is set up as a square of (2 * order + gap) * order cells on a side, with the cells in the gap being unused. The sets used are the same as for sudoku of the same order, but with 'g0' through 'g4' prepended to their names, with g0 being the top left sudoku grid, g1 the top right, g2 the middle, g3 the bottom left, and g4 the bottom right.

In the case of the 's' sets, this would result in duplicate sets being generated in the overlap area, so the 's' set from the higher-numbered grid is suppressed. For example, in the 'Samurai Sudoku' configuration, sets g0s8, g1s6, g2s6, and g2s8 contain exactly the same cells as g2s0, g2s2, g3s2, and g4s0 respectively, so the latter are suppressed, and only the former appear in the topology.

Problems are specified left-to-right by rows. The cells in the gaps are unused, and are not specified. For example, the May 2, 2008 'Samurai Sudoku' problem could be specified as

`````` . . .  . . 1  . . .         . . .  4 . .  . . .
. . .  . 3 .  6 . .         . . 7  . 2 .  . . .
. . .  7 . .  . 5 .         . 4 .  . . 5  . . .

. . 6  9 . .  . . 7         6 . .  . . 9  1 . .
. 5 .  . 2 .  . 4 .         . 2 .  . 5 .  . 9 .
4 . .  . . 5  2 . .         . . 8  1 . .  . . 7

. 2 .  . . 4  . . .  . 8 .  . . .  3 . .  . 2 .
. . 5  . 6 .  . . .  4 . 5  . . .  . 8 .  4 . .
. . .  1 . .  . . .  . 7 .  . . .  . . 7  . . .

. 4 .  . 6 .  . 2 .
6 . 7  8 . 9  4 . 1
. 1 .  . 4 .  . 3 .

. . .  7 . .  . . .  . 9 .  . . .  . . 6  . . .
. . 8  . 2 .  . . .  2 . 8  . . .  . 8 .  5 . .
. 4 .  . . 3  . . .  . 5 .  . . .  3 . .  . 2 .

2 . .  . . 7  8 . .         . . 4  1 . .  . . 6
. 3 .  . 5 .  . 4 .         . 3 .  . 2 .  . 4 .
. . 4  8 . .  . . 7         2 . .  . . 3  1 . .

. . .  9 . .  . 1 .         . 5 .  . . 8  . . .
. . .  . 6 .  9 . .         . . 7  . 4 .  . . .
. . .  . . 4  . . .         . . .  2 . .  . . .``````

Setting this attribute causes the rows and columns attributes to be set to (2 * order + gap) * order. The symbols attribute is set to '.' and the numbers 1, 2, ... up to order * order.

rows (number)

This attribute defines the number of lines of output to present before inserting a blank line (for readability) when formatting the topology attribute, or the solution to a puzzle.

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 the `brick` attribute 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 the `brick` attribute 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,d2 r3,c2       r3,c3,d1``````

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.

For certain topologies (e.g. the London Times Quincunx) it may be convenient to include in the definition cells that are not part of the puzzle. Such unused cells are defined by specifying just a comma, without any set names.

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

## Methods

This package provides the following public methods:

## new

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

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

## copy

`` \$su->copy ()``

This method copies the current problem to the clipboard. If solution() has been called, the current solution goes on the clipboard.

See CLIPBOARD SUPPORT for what is needed for this to work.

## drop_set

`` \$su->drop_set( \$name )``

This method removes from the current topology the set with the given name. The set must exist, or an exception is raised.

## generate

`` \$problem = \$su->generate( \$min, \$max, \$const );``

This method generates a problem and returns it.

The \$min argument is the minimum number of givens in the puzzle. You may (and probably will) get more. The default is the number of cells in the puzzle divided by the number of sets a cell belongs to.

The value of this argument is critical to getting a puzzle: too large and you generate puzzles with no solution; too small and you spend all your time backtracking. There is no science behind the default, just an attempt to make a rational heuristic based on the number of degrees of freedom and the observation that about a third of the cells are given in a typical Sudoku puzzle. My experience with the default is:

`````` topology        comment
brick 3,2       default is OK
corresponding 3 default is OK
cube 3          default is too large
cube half       default is OK
cube full       default is OK
quincunx 3      default is too large
sudoku 3        default is OK
sudoku 4        default is OK
sudokux 3       default is OK``````

Typically when I take the defaults I get a puzzle in anywhere from a few seconds (most of the listed topologies) to a couple minutes (sudoku 4) on an 800 Mhz G4. But I have never successfully generated a Dion cube (cube 3). `Caveat user.`

The \$max argument is the maximum number of givens in the puzzle. You may get less. The default is 1.5 times the minimum.

The \$const argument specifies the constraints to be used in the generated puzzle. This may be specified either as a string or as a hash reference. If specified as a string, it is a whitespace-delimited list, with each constraint name possibly followed by an equals sign and a number to specify that that constraint can be used only a certain number of times. For example, 'F N ?=1' specifies a puzzle to be solved by use of any number of applications of the F and N constraints, and at most one guessed cell. If specified as a hash reference, the keys are the constraint names, and the values are the usage counts, with undef meaning no limit. The hash reference corresponding to 'F N ?=1' is {F => undef, N => undef, '?' => 1}. The default for this argument is to allow all known constraints except '?'.

In practice, the generator usually generates puzzles solvable using only the F constraint, or the F and N constraints.

The algorithm used is to generate a puzzle with the minimum number of cells selected at random, and then solve it. If a solution does not exist, we try again until we have tried `generation_limit` times, then we return undef. This means generate() is not guaranteed to generate a puzzle.

If we get a solution, we remove allowed constraints. If we run into a constraint that is not allowed, we either stop (if we're below the maximum number of givens) or turn it into a given value (if we're above the maximum). We stop unconditionally if we get down to the minimum number of givens. As a side effect, the generated puzzle is set up as a problem.

Note that if you allow guesses you may get puzzles with more than one solution.

## get

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

## paste

`` \$su->paste()``

This method pastes a problem from the clipboard.

See CLIPBOARD SUPPORT for what is needed for this to work.

## problem

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

## set

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

## solution

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

## steps

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

`` \$string = \$su->unload();``

This method returns either the current puzzle or the current solution, depending on whether the solution() method has been called since the puzzle was loaded.

# EXECUTABLES

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

# CLIPBOARD SUPPORT

Clipboard support is via the Clipboard module. If this is not installed, the `copy()` and `paste()` methods will throw exceptions.

# 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 author 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 number 41 for September 5 2005 ("Sudoku Variations", http://mathpuzzle.com/MAA/41-Sudoku%20Variations/mathgames_09_05_05.html) provided a treasure trove of 'non-standard' Sudoku puzzles.

The `Games-LogicPuzzle` package by Andy Adler (see http://metacpan.org/release/Games-LogicPuzzle/) solves all sorts of combinatorial puzzles, by backtracking through the puzzle space and applying a user-supplied function to see whether it has a valid solution. The examples include a couple Sudoku puzzles.

The `Games-Sudoku` package by Eugene Kulesha (see `http://metacpan.org/release/Games-Sudoku/`) solves the standard 9x9 version of the puzzle. As of June 15 2019 this appears to have been retracted.

The `Games-Sudoku-Component` package by Kenichi Ishigaki (see http://metacpan.org/release/Games-Sudoku-Component/) both generates and solves the standard 9x9 version of the puzzle.

The `Games-Sudoku-Component-TkPlayer` by Kenichi Ishigaki (see http://metacpan.org/release/Games-Sudoku-Component-TkPlayer/). Tk front end for his Games-Sudoku-Component.

The `Games-Sudoku-CPSearch` package by Martin-Louis Bright (see https://metacpan.org/release/Games-Sudoku-CPSearch). Solves 9x9 Sudoku by use of "F" and "N" constraints and backtracking.

The `Games-Sudoku-Lite package` by Bob O'Neill (see http://metacpan.org/release/Games-Sudoku-Lite/) solves the standard 9x9 version of the puzzle.

The `Games-Sudoku-OO` package by Michael Cope (see http://metacpan.org/release/Games-Sudoku-OO/) 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 extensible to other topologies than the standard one.

The `Games-Sudoku-Solver` package by Fritz Mehner (see http://metacpan.org/release/Games-Sudoku-Solver/) solves 9x9 Sudoku puzzles by recursion and backtracking.

The `Games-Sudoku-SudokuTk` package by Christian Guine (see http://metacpan.org/release/Games-Sudoku-SudokuTk/ claims to implement a Tk-based Sudoku solver.

The `Games-YASudoku` package by Andrew Wyllie (see http://metacpan.org/release/Games-YASudoku/) 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)