sudokug - Script to solve sudoku-like puzzles.

MODIFICATIONS
AUTHOR
COPYRIGHT

NAME

sudokug - Script to solve sudoku-like puzzles.

SYNOPSIS

 $ sudokug

 (front matter displayed here)

 sudokug> problem <<eod
 eod: . . . 4 . . 7 8 9
 eod: 4 . 6 . . . 1 . .
 eod: . 8 . . . . . 5 .
 eod: 2 . 4 . . 5 . . .
 eod: . 9 5 . . . . . .
 eod: . . . 9 . 2 3 4 5
 eod: . 3 . . 7 . 9 . 8
 eod: . 6 7 . . 1 . . .
 eod: 9 . . . . 8 . . 2
 eod: eod
 sudokug> solution
 1 2 3 4 5 6 7 8 9
 4 5 6 7 8 9 1 2 3
 7 8 9 1 2 3 4 5 6
 2 1 4 3 6 5 8 9 7
 3 9 5 8 4 7 2 6 1
 6 7 8 9 1 2 3 4 5
 5 3 2 6 7 4 9 1 8
 8 6 7 2 9 1 5 3 4
 9 4 1 5 3 8 6 7 2
 sudokug> solution
 No solution found
 sudokug> exit

DETAILS

This Perl script is based on the Games::Sudoku::General module. It is capable of solving a variety of Sudoku and Sudoku-like puzzles. In fact, it should be able to solve any puzzle that meets the following criteria:

* The puzzle is based on allocating symbols among cells.

* Each cell contains exactly one symbol.

* A number of sets of cells are specified; each set must contain each symbol exactly once.

* Optionally, some cells may contain initial values.

* Optionally, some cells may be restricted to a subset of all possible symbols.

In theory, any size and topology is possible. What is not possible at the moment is the solution of puzzles requiring logic other than that given above.

There is one command option: -filter, which suppresses the front matter to make the script behave more like a traditional Unix filter. Commands may be piped or redirected in (e.g.

 sudokug <commands

 cat commands | sudokug

) if the user so desires, with or without the -filter option.

Basically, any exposed method in Games::Sudoku::General is a command understood by this script. Arguments to the methods are parameters to the script commands. A few commands have been added to make life for the user of the script easier.

Commands are parsed by Text::ParseWords, so the command name and parameters are whitespace-delimited. Any parameter that contains whitespace must be quoted. Either single (``''') or double ('``') quotes will work.

Because some of the parameters (e.g. specifying a problem) involve a large number of bytes, pseudo-``here documents'' are supported. To specify a ``here document'' as a parameter, specify ``<<string'' in place of the parameter. The script will prompt with the string, and anything you enter is part of that parameter, until you enter a line consisting solely of the given string. More than one ``here document'' can be specified; you will be prompted for them in left-to-right order. There is an example of a ``here document'' in the SYNOPSIS section.

Below is a brief description of the commands. For the attributes that may be set or retrieved, and a more thorough (and possibly more current) discussion of the underlying methods, see the Games::Sudoku::General manpage, or (equivalently) use the command

 sudokug> help lib

Commands

add_set

This command adds a set to an existing topology. The arguments are the name of the new set, and the numbers of the existing cells that are to be members of it.

Cells are numbered from 0 in the order in which they were defined by the topology. Typically this is row order.

constraints_used

This command lists the constraints used to provide the most recent solution.

copy

Copy the current puzzle or solution to the clipboard. See the CLIPBOARD SUPPORT section of the the Games::Sudoku::General manpage documentation for what you need to make this work.

exit

This command does not correspond to a Games::Sudoku::General method. It causes this script to terminate. Entering end-of-file in response to a prompt by this script also works.

generate min max constraints

This command attempts to generate a puzzle in the current topology. All arguments may be defaulted, but the defaults may not be appropriate for all topologies. See 'help lib' for details.

get name ...

This command displays the values of the named attributes. You can specify the name of more than one attribute. See Attributes below for a brief discussion of each, and the Games::Sudoku::General manpage for more details.

help

This command does not correspond to a Games::Sudoku::General method. Without an argument, it gets you this documentation. If given with the argument 'lib', that is, as

 sudokug> help lib

it gets you the POD for Games::Sudoku::General.

new

This command instantiates a Games::Sudoku::General object. You get one for free when you launch this script; this command is for those cases when it is easier to start over with a new object than to reconfigure the one you already have. Any arguments get passed to the set() method.

paste

Paste a new puzzle from the clipboard. See the CLIPBOARD SUPPORT section of the the Games::Sudoku::General manpage documentation for what you need to make this work.

problem string

This command specifies the problem to be solved, in the order they were defined by the topology (typically row order). The problem string must be specified in terms of the currently-valid symbols. Whitespace between the symbols is always allowed, but is required only if at least one symbol consists of more than one character. Any invalid symbol is taken to represent an unspecified cell.

Line breaks may be given (as in the SYNOPSIS), but are treated like any other whitespace.

set name value ...

This command sets each named attribute to its given value. You can specify more than one name/value pair. See Attributes below for a brief discussion of each, and the Games::Sudoku::General manpage for more details.

show name ...

This command does not correspond to a Games::Sudoku::General method, but is just a synonym for 'get'.

solution

This command causes an attempt to solve the currently-set-up problem. If a solution is found, it will be displayed. Otherwise you will get a brief message saying what happened.

If you issue this command more than once without an intervening 'problem' command, the solution will be attempted starting where the previous solution left off. If there are multiple solutions to a puzzle, each 'solution' command will get you one, until you run out.

source filename

This command does not correspond to a Games::Sudoku::General method. It causes subsequent commands to be taken from the given file, until the file is completely read, or until an 'exit' command is executed. 'source' commands may be nested to the limit allowed by your system.

'.' is accepted as a synonym for 'source', but the whitespace before the file name is still required.

steps

This command displays the steps taken to obtain the most recent solution. They will be displayed as follows:

F [cell value] - this represents a forced cell. That is, the given value is the only allowed value for the cell. The given cell is set to that value.

N [cell value] - this represents a ``numeration''. That is, the given value can only be supplied by the given cell. The given cell is set to that value.

B [[cell cell ...] value] - ``box claim''. The given value is not possible in the given cells, because they lie outside a set intersection that must contain that value. The given value is eliminated as a possibility for the given cells.

T naked size [[cell cell ...] value] ... - ``naked tuple''. The given value is not possible for the given cell because there exists a ``tuple'' (pair, triple, ...) of cells of the given size which must contain this value, and the given cells are not in the tuple. More than one value can be given, with a list of cells for each. The given value is eliminated as a possibility for the given cells.

T hidden size [[cell cell ...] value] ... - ``hidden tuple''. The given cells are part of a ``tuple'' of cells of the given size that must contain a same-sized ``tuple'' of values, but the given values are not part of the ``tuple'' of values that must be contained in those cells. The given value is eliminated as a possibility for the given cell.

? [cell value] - ``backtrack''. If derivation of the solution reaches a point where none of the above rules can be applied, we simply take a guess at a legal cell value. The cell with the smallest number of possible values is chosen for the guess. If there are more than one such cell, the one with the smallest cell number is chosen. If at any point a solution becomes impossible, we backtrack to the point we took the guess, and try the next possible value.

unload

Display the current problem, or its current solution if it has been solved.

Attributes

Any readable attribute may be displayed with the 'get' or 'show' commands, and any writable attribute may be set with the 'set' command. For example:

 sudokug> set allowed_symbols <<eod
 eod: e=2,4,6,8
 eod: o=1,3,5,7,9
 eod: eod
 sudokug>

The following simply lists the attributes. Rather than repeat their definitions, you are simply referred to the Games::Sudoku::General manpage, or (equivalently) to the

 sudokug> help lib

command.

allowed_symbols (string)

This attribute is used to specify and name sets of allowed symbols. See above for an example.

autocopy (boolean)

If true (in the Perl sense) generated problems are copied to the clipboard.

brick (string, write-only)

This pseudo-attribute sets the topology, symbols, and columns for a Sudoku puzzle involving rectangular regions rather than square ones. The value is a comma-delimited string of three numbers representing the horizontal and vertical dimensions of the rectangular regions, and the size of the enclosing square.

The last number may be omitted, with the default being the product of the first two. It is in fact deprecated, with the intent of disallowing it in the future.

columns (number)

This attribute specifies the number of cells displayed on a line of topology or solution output. It has nothing to do with the problem itself, and no effect on problem input.

corresponding (number)

This pseudo-attribute sets the topology, symbols, and columns for a Sudoku puzzle having the additional restriction that corresponding cells in the small squares must contain different numbers. The value is the size of the small square (i.e. the same as the value for sudoku. Also called ``disjoint groups''.

cube (string, write-only)

This pseudo-attribute sets the topology, symbols, and columns for a Sudoku puzzle on the faces of a cube. There are three topologies supported; two on the face of a 4 x 4 x 4 cube, plus the Dion cube. Which one is actually generated is selected by the argument:

* a number generates a Dion cube, and specifies the size of the small square. Specifying 3 generates a 9 x 9 x 9 Dion cube.

* 'full' generates a puzzle on all 6 faces of the cube. The sets are the faces of the cube and the ``stripes'' of cells running around the cube in all three directions. The problem is entered face-by-face; if you imagine the cube unfolded into a Latin cross, work top-to-bottom and left-to-right.

* 'half' generates a puzzle on the visible 3 faces of an isometric view of a cube. The sets are halves of the face and the visible ``stripes''. Imagine the visible part of the cube unfolded into the letter ``L'', with the top and right faces divided horizontally, and the remaining face divided vertically. Enter the problem working top-to-bottom and left-to-right.

Caveat: The symbols generated for a 'full' cube are 1 .. 16. The example I have (from http://www.mathrec.org/sudoku/sudokucube.gif) uses 0 through F. If you have one of these, remember to 'set symbols' after you 'set cube full'.

See the Games::Sudoku::General manpage (or 'help lib') for a fuller discussion, with cheesy typed diagrams.

debug (number)

This attribute displays debugging information. The only supported value is 0.

generation_limit (number)

This attribute sets the number of times the generate command tries to generate a puzzle before it gives up.

iteration_limit (number)

This attribute sets the number of times the solution command is allowed to use the backtrack constraint. If set to 0, there is no limit.

largest_set (number, read-only)

This attribute reports the size of the largest set in the current topology.

latin (number, write-only)

This pseudo-attribute sets the topology to a Latin square, and the symbol set to the requisite number of letters. The argument is the size of the square.

max_tuple (number)

This attribute is the maximum tuple size considered when applying the tuple constraint.

name (string)

This is just a convenient place to put an identifying string.

output_delimiter (string)

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

rows (number)

This attribute specifies the number of lines of topology or solution output before a blank line is inserted for readability. It has nothing to do with the problem itself, and no effect on problem input.

status_text (string, read-only)

This attribute reports the message generated by the last attempted solution.

status_value (number)

This attribute is the status code generated by the last attempted solution.

sudoku (number, write-only)

This pseudo-attribute sets the topology, symbols, and columns for the usual Sudoku puzzle, The value is the 'order' of the puzzle, that is, the size of the small square. To get the usual set-up, use

 sudokug> set sudoku 3

sudokux (number, write-only)

This pseudo-attribute is similar to the 'sudoku' attribute, but the main diagonals are included.

symbols 'string'

This attribute sets the symbols that are to be placed in the cells of the puzzle. The individual symbols must be whitespace-delimited, and the first symbol must be the 'canonical' representation of an empty cell.

topology (string)

This attribute sets the current topology in terms of a list of the sets to which each cell belongs.

MODIFICATIONS

 0.001 T. R. Wyant
   Initial release
 0.003 T. R. Wyant
   Documented methods and attributes added
   since 0.001.
 0.004 T. R. Wyant - Documented new use of cube attribute.
 0.005 T. R. Wyant - Documented new methods and attributes.
 0.006 T. R. Wyant
   Corrected spelling.
   Allowed input to be redirected or piped in.
   Added -filter option.
   Document new methods and attribites

AUTHOR

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

COPYRIGHT

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

sudokug - Script to solve sudoku-like puzzles.