# [RFC] Games::Sudoku::General

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on

All,

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(<<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 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"

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.

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.

## Re: [RFC] Games::Sudoku::General

Can your module also solve Sudoku boards like this one:

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

It should, I guess, be able to solve this if it really is a
general module -- and also be able to solve 4x4 (64 square)
sudokus.  I am also writing on a Games::Sudoku::General module,
and that one can solve puzzles like the above, and also 4x4 and
5x5 etc., but I'm not sure when I'll get it completed.

Peter

--
#!/local/bin/perl5 -wp -*- mode: cperl; coding: iso-8859-1; -*-
# matlab comment stripper (strips comments from Matlab m-files)
s/^((?:(?:[])}\w.]'+|[^'%])+|'[^'\n]*(?:''[^'\n]*)*')*).*/\$1/x;

## Re: [RFC] Games::Sudoku::General

Peter J. Acklam wrote:

Great minds run in the same track. Or two fools with a single thought. ;-)

So far my "weird examples" are from
http://www.maa.org/editorial/mathgames/mathgames_09_05_05.html

I have problems like figures 1-5, 8, and 10a in my test suite.

I believe my version would solve figure 13 (left-hand side) if I ever
got around to reducing their 7-segment display patterns to lists of
legal values. I'm not sure what he's getting at with figure 13
(right-hand side), but if we're to derive minimum value (and maybe
parity) from the pips, I think it will do the right-hand side also.

I see no reason why it would not do the London Times Quincunx (figure
15), but getting the topology entered is going to be a major pain.

On the other hand, figure 9 (some cells take multiple values) is going
to be a little work, though I think I know how to proceed. Figure 10b
(dominos) would take a lot more work, and I'm not sure I can see getting
there. But since I'm taking a set-theoretic approach, it's at least
theoretically possible.

I do not imagine doing figures 7, 11 and 12 with my implementation. What
I have done is basically set-theoretic, and these figures make use of
the values of the numbers.

What I have at the moment is a big honkin' module. I can imagine
splitting relevant functionality into

Games::Sudoku::General (representing the topology)

Games::Sudoku::General::Cell

Games::Sudoku::General::Set (representing rows, columns ...)

Games::Sudoku::General::Constraint (constraints on the values)
Games::Sudoku::General::Constraint::F (forced values)
Games::Sudoku::General::Constraint::N (numeration)
Games::Sudoku::General::Constraint::B (box claim)
Games::Sudoku::General::Constraint::T (tuple)
Games::Sudoku::General::Constraint::X (not yet written in any form)
Games::Sudoku::General::Constraint::Y (not yet written in any form)
Games::Sudoku::General::Constraint::W (not yet written in any form)
Games::Sudoku::General::Constraint::Backtrack

This way one could write arbitrary rules into the class, and maybe do
some of the ones I said I didn't imagine doing. But whether this will
happen I can't say.

Tom