[Haskell-cafe] Code Review: Sudoku solver
Claus Reinke
claus.reinke at talk21.com
Mon Apr 3 12:24:35 EDT 2006
>> > 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
More information about the Haskell-Cafe
mailing list