[Haskell-cafe] Code Review: Sudoku solver

[Chris Kuklewicz]

Claus Reinke wrote:
>>> > It solves sudoku puzzles.  (What pleasure do people get by doing >
>>> these in their heads?!?)
> 
> probably the same you get from writing programs?-) figuring out the
> rules, not getting lost in complexity, making something difficult work..

>From a human standpoint, there are some puzzles that are much harder than
others.  This also applies to the few programs that I have seen.  It is this
variety of complexity that makes it interesting.

>>> They are probably asking the same question: why take hours to write a
>>> program to do it when with my mad sudoku solving skills I can solve it
>>> in X seconds? My roommate is like this.
> 
> if we just throw raw computing power at the problem (in-place array
> updates, bitvectors, multiprocessors, ..), wouldn't they be justified?
> but as soon as we try to take their skills and encode them in our
> programs, things become more interesting (do computers really "play"
> chess?-).

You can go get the 36,628 distict minimal puzzles from
http://www.csse.uwa.edu.au/~gordon/sudokumin.php that have only 17 clues.
Then you can run all of them through your program to locate the most evil ones,
and use them on your associates.  :)

This also gave me a way to statistically measure if a new deductive step made
much of a difference (or if it made no difference).  Histograms and gnuplot helped.

> [snip Curry language example]

> my own Sudoku solver (yes, me too - see attached, but only after
> you've written your own!-) uses simple hand-coded constraint propagation
> to limit the space for exhaustive search - some puzzles are solved by
> constraint propagation only, and even where guesses are used, each guess
> is immediately followed by propagation, to weed out useless branches
> early, and to deduce consequences of each guess before asking for the
> next one. the good old game, start with generate&test, then move the
> tests forward, into the
> generator.
> 
> I've only coded the two most useful groups of constraints (when
> there's only a single number left for a position, or when there is
> only a single position left for a number). there are other deductions
> one does in by-hand solving, and I'm not an experienced sudoku solver
> myself, so I don't even know more than a few such rules yet, but these
> particular two seem sufficient to get acceptable performance even under
> ghci/hugs, so why do more?-) (*)

I have two versions of a solver.  The first is a re-write of GDANCE bu Knuth to
solve Sudoku efficiently as a binary cover problem. (see
http://www-cs-faculty.stanford.edu/~knuth/programs.html )  This uses the
"Dancing Links algorithm" implemented with STRef's and is very fast.

The second uses a different encoding to look for clever deductions. This alone
solves some easy problems and comes very close before getting stuck on most.
There are few though that start with 17 hints and only discover one or two more
by logic before getting stuck.  These are the most evil of all.

You might be interested in the deductions described at
http://www.sudokusolver.co.uk/

> 
> [by acceptable, I mean that my sequence of 5 test puzzles is solved in
> less than 20 seconds on a 2GHz Pentium M; no idea how that compares to
> the most efficient solvers]

I could run ~20,000 puzzles in a couple of hours.  (The collection was smaller
then).

> perhaps Haskell should have Control.Constraint.* libraries for
> generalized constraint propagation (and presumably for constraint
> handling rules as well, as they are so popular nowadays for specifying
> Haskell's type classes)?

Did you see the monad at http://haskell.org/hawiki/SudokuSolver ?  Perhaps you
could generalize that.

> 
> cheers,
> claus
> 
> (*) actually, that was a bit disappointing!-( I was hoping    for some
> fun while trying to encode more and more
>    "clever" rules, but not much of that seems to be required.
> 

You need more than 5 examples.  The truly evil puzzles are rarer than that.  Go
get the set of minimal puzzles and see how far your logic takes you.

-- 
Chris