/ 
Games-Sudoku-General-0.001
River stage zero No dependents
/ sudokug

NAME

sudokug - Executable to solve sudoku-like puzzles.

SYNOPSIS

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

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 this in the "SUMMARY" 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 Games::Sudoku::General, or (equivalently) use the command

sudokug> help lib

Commands

constraints_used

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

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.

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 Games::Sudoku::General 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's easier to start over with a new object than to reconfigure the one you already have.

problem string

This command specifies the problem to be solved, in 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 Games::Sudoku::General for more details.

show name ...

This command does not corespond 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 [[cell cell ...] value] ... - "naked tuple". The given value is not possible for the given cell because there exists a "tuple" (pair, triple, ...) of cells 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 [[cell cell ...] value] ... - "hidden tuple". The given cells are part of a "tuple" of cells 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.

Attributes

Any readable attribute may be displayed with the 'get' or 'show' commands, and any writeable 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 Games::Sudoku::General, 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.

columns (number)

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

debug (number)

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

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.

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.

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.

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.

AUTHOR

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

COPYRIGHT

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

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