[Haskell-cafe] Code Review: Sudoku solver

[Claus Reinke]

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

>> 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?-).
 
> I would say because they have chosen the wrong language for this
> problem :-) Solving Sudoku is a typical finite domain constraint
> problem. Thus, a language with constraint solving facilities
> like Curry (a combination of Haskell and constraint logic programming)
> is much better suited. Actually, I wrote a Sudoku solver in Curry
> and the actual code for the solver is 10 lines of code which is
> compact and well readable (if you are familiar with Haskell), see
> 
> http://www.informatik.uni-kiel.de/~curry/examples/CLP/sudoku.curry

interesting. I haven't yet got round to installing Curry and trying this,
but I assume that this declarative specification, under a finite domain
constraint solver, is not just an effective implementation, but an efficient
one, right? 

if yes, it is really impressive how constraint propagation has managed 
to make essentially the same code that, as a mere functional logic 
program, would be effective, but hardly useable, so much more 
efficient, just by imposing a different evaluation strategy on it. and 
the factoring into constraint generation and constraint propagation 
under some strategy is nice as well.

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?-) (*)

[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]

since I haven't factored out the constraint propagation into a
general module, the core of my code is a lot longer than the 
Curry version (about 60 additional lines, though I'm sure one 
could reduce that;-). the only negative point I can find about 
the Curry example is that it isn't obvious what tricks the 
FD-constraint solver is using (ie., it would be nice to have 
a concise language for expressing propagation techniques, 
and then explicitly to apply a strategy to the declarative 
specification, instead of the implicit, fixed strategy of the 
built-in solver).

for instance, I assume that Michael's declarative specification
implicitly allows the built-in solver to use the first group of 
constraints I mentioned (only a single possible number left 
for a position), but does it use the second group (only a single 
position left to place a number in a particular line/column/block)? 
my guess is that no, it doesn't, although it wouldn't be difficult 
to change that - just have the declarative specification express 
the dual puzzle as well (assigning positions to numbers instead 
of numbers to positions). 

is this correct, or is that dual reading already implied?

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

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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Sudoku.hs
Type: application/octet-stream
Size: 6861 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060403/294cc411/Sudoku.obj