[RFC] Games::Sudoku::General
am 30.11.2005 23:58:28 von unknownAll,
Do we really need another Sudoku package? Well, maybe. This note is to
solicit comments on the proposed Games::Sudoku::General. The "General"
is because in addition to the standard puzzle it solves a variety of
related puzzles of the "allocate objects among intersecting sets" kind.
The intent is also to solve the puzzle as much as possible by logic
rather than backtracking, and to be able to report what rules were used
in the solution.
Relevant (I hope!) portions of the POD as it now stands are appended.
Thank you very much,
Tom Wyant (mailing address to the contrary notwithstanding).
NAME
Games::Sudoku::General - Solve sudoku-like puzzles.
SYNOPSIS
$su = Games::Sudoku::General->new ();
print $su->problem(<
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 puzzle includes
the game known as 'Sudoku', 'Number Place', or '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
accomodated by defining named constraints in terms of the
values allowed, and then giving the constraint name for each
unoccupied cell to which it applies. See "symbol_constraint"
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.
SEE ALSO
The Games-Sudoku package by Eugene Kulesha solves the
standard 9x9 version of the puzzle.
The Games-Sudoku-OO package by Michael Cope 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 extensable to other topologies
than the standard one.
The Games-YASudoku package by Andrew Wyllie 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.