[RFC] Games::Sudoku::General

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

Threaded View


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).

     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

     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.

     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.


#!/local/bin/perl5 -wp -*- mode: cperl; coding: iso-8859-1; -*-
# matlab comment stripper (strips comments from Matlab m-files)

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

Peter J. Acklam wrote:
Quoted text here. Click to load it

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

So far my "weird examples" are from

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::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)

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.


Site Timeline