Tom Wyant > Games-Sudoku-General-0.013 > Games::Sudoku::General

Download:
Games-Sudoku-General-0.013.tar.gz

Dependencies

Annotate this POD

CPAN RT

Open  0
View/Report Bugs
Module Version: 0.013   Source   Latest Release: Games-Sudoku-General-0.015

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 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/dist/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 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.

Beginning with version 0.005_01, the overall size value is optional, and defaults to the product of the horizontal and vertical dimensions. Note that I am strongly considering eliminating this value, since it appears to me that any value other than the default results in an impossible puzzle. As of version 0.005_01, specification of the third value is deprecated.

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

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.

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.

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 (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, 6])
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.

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

$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

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

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

$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,6     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.

$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->paste ()

This method pastes a problem from the clipboard.

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

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

$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 highly OS-specific. Here is the story by OS - or, really, by the contents of $^O:

cygwin

Under cygwin, we first try to load the Win32::Clipboard module. If this succeeds, we use it. If not, we try to use the xclip program, available from http://freshmeat.net/project/xclip.

darwin

Under Darwin, also known as Mac OS X, we use the pbcopy programs to copy text to the clipboard, and pbpaste to retrieve text from the clipboard. These programs are supposed to come with Mac OS X. If pbcopy or pbpaste (depending on what we are trying to do) is not found, we try xclip, under the assumption that you are running Darwin without the Mac OS X overlay. The xclip program is available from http://freshmeat.net/project/xclip.

MacOS

Under MacOS (meaning OS 9 or below) we currently have no way to put text onto the clipboard.

MSWin32

Under Windows, we use Win32::Clipboard if available.

Anything else

Under any other operating system, we try to use the xclip program, available from http://freshmeat.net/project/xclip.

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 for September 5 2005 (http://www.maa.org/editorial/mathgames/mathgames_09_05_05.html) provided a treasure trove of 'non-standard' Sudoku puzzles.

SEE ALSO ^

The Games-LogicPuzzle package by Andy Adler (see http://search.cpan.org/dist/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://search.cpan.org/dist/Games-Sudoku/) solves the standard 9x9 version of the puzzle.

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

The Games-Sudoku-Component-TkPlayer by Kenichi Ishigaki (see http://search.cpan.org/dist/Games-Sudoku-Component-TkPlayer/). Tk front end for his Games-Sudoku-Component.

The Games-Sudoku-CPSearch package by Martin-Louis Bright (see http://search.cpan.prg/dist/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://search.cpan.org/dist/Games-Sudoku-Lite/) solves the standard 9x9 version of the puzzle.

The Games-Sudoku-OO package by Michael Cope (see http://search.cpan.org/dist/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://search.cpan.org/dist/Games-Sudoku-Solver/) solves 9x9 Sudoku puzzles by recursion and backtracking.

The Games-Sudoku-SudokuTk package by Christian Guine (see http://search.cpan.org/dist/Games-Sudoku-SudokuTk/ claims to implement a Tk-based Sudoku solver.

The Games-YASudoku package by Andrew Wyllie (see http://search.cpan.org/dist/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)

COPYRIGHT AND LICENSE ^

Copyright (C) 2005, 2006, 2008, 2011 by Thomas R. Wyant, III

This program is free software; you can redistribute it and/or modify it under the same terms as Perl 5.10.0. For more details, see the full text of the licenses in the directory LICENSES.

This program is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose.

syntax highlighting: