[Haskell-cafe] Code Review: Sudoku solver
Claus Reinke
claus.reinke at talk21.com
Fri Apr 7 11:33:36 EDT 2006
> 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
More information about the Haskell-Cafe
mailing list