[Haskell-cafe] Code Review: Sudoku solver

[Claus Reinke]

> Just out of curiosity, speed was not the objective when I wrote my solver, I 
> wanted to avoid guesswork (as much as possible), but in comparison with Cale 
> Gibbard's and Alson Kemp's solvers (which are much more beautifully coded), 
> it turned out that mine is blazingly fast, so are there faster solvers around 
> (in Haskell, in other languages)?

if I modify your solver to produce similar output to mine (input/first 
propagation, solved puzzle, number and list of guesses made), your's 
takes about a third of the time of mine (solving 36628 17hint puzzles 
in 6m vs 17m, 2GHz Pentium M), and I wasn't exactly unhappy with 
my solver before I did this comparison!-)

like you, I've been trying to remove guesses, and the speed came as a
welcome bonus (I'm still using lists all over the place, with lots of not
nice adhoc code still remaining; not all propagators are iterated fully
yet because I only recently removed a logic bug that slowed down the
search instead of speading it up; ..). so the more interesting bit is that 
our solvers disagree on which are the most difficult puzzles (requiring 
the largest number of guesses):

df
puzzles involving guesses: 5319
largest number of guesses: 
    10 (#36084), 11 (#22495)

cr
puzzles involving guesses: 8165
largest number of guesses: 
    10 (#9175), 10 (#17200), 10 (#29823), 10 (#30811)

df's solver needs 0/0/3/0 for cr's trouble spots, while cr's solver needs 
5/9 guesses for df's. lots of potential for interesting investigations, though
mostly for me!-)

cheers,
claus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Sudoku.hs
Type: application/octet-stream
Size: 12124 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060407/de88ba51/Sudoku.obj