|
Games::Sudoku::General - Solve sudoku-like puzzles. |
Games::Sudoku::General - Solve sudoku-like puzzles.
$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
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.
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.
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.
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.
generate() method to implicitly call
copy() to copy the generated problem to the clipboard.
This attribute is false by default.
$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.
This kind of puzzle is also called ``disjoint groups.''
* 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
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.
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.
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.
The default is 4, meaning that the solution considers doubles, triples, and quads only.
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.
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.
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.
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.
Setting the topology invalidates any currently-set-up problem.
This package provides the following public methods:
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.
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.
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
solution()
has been called, the current solution goes on the clipboard.
See CLIPBOARD SUPPORT for what is needed for this to work.
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 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 must 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.
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.
See CLIPBOARD SUPPORT for what is needed for this to work.
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.
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.
problem() method has not been called,
an exception is thrown.
Status values set:
SUDOKU_SUCCESS SUDOKU_NO_SOLUTION SUDOKU_TOO_HARD
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.
solution() method has been called since the
puzzle was loaded.
The distribution for this module also contains the script 'sudokug', which is a command-driven interface to this module.
Clipboard support is highly OS-specific. Here is the story by OS - or, really, by the contents of $^O:
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.
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.
Under MacOS (meaning OS 9 or below) we currently have no way to put text onto the clipboard.
Under Windows, we use Win32::Clipboard if available.
Under any other operating system, we try to use the xclip program, available from http://freshmeat.net/project/xclip.
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.
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.
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.
0.004 T. R. Wyant
Added Dion cube (via 'set cube number').
0.005 T. R. Wyant
Added generate() method and generation_limit
attribute.
Added rows attribute. This changes the default
output for 'multi-faced' puzzles.
0.006 T. R. Wyant
Fixed problem with 'set corresponding'. Thanks
to David Jelinek of Central Michigan University
for diagnosing the problem and finding a
solution.
Corrected spelling.
Eliminated Scalar::Util::looks_like_number, since
apparently ActivePerl does not have it.
Add copy() method and autocopy attribute, for getting
generated puzzles onto the clipboard.
Add paste() method, for loading puzzles from the
clipboard.
Add unload() method.
0.007 T. R. Wyant
Corrected example in topology attribute documentation,
and other documentation tweaks.
Moved General.pm to lib/Games/Sudoku.
Added Build.PL
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-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-SudokuTk package by Christian Guine (see http://search.cpan.org/dist/Games-Sudoku-SudokuTk/ claims to implement a Tk-based Sudoku solver, but as of version 0.05 the kit seems to be incomplete.
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.
Thomas R. Wyant, III (wyant at cpan dot org)
Copyright 2005, 2006 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.
|
Games::Sudoku::General - Solve sudoku-like puzzles. |