[Haskell-cafe] Code Review: Sudoku solver

Daniel Fischer daniel.is.fischer at web.de
Fri Apr 7 20:20:55 EDT 2006


Am Freitag, 7. April 2006 17:33 schrieben Sie:
> > 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!-)

Mine's even faster now (at least on my computer, would you care to test it on 
your's? If you don't want to get EnumSet, just change DiffArray to Array, 
worked wonders for me), I'll dig into yours tomorrow to see what I can get 
out of it to improve my algorithm.

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

lists and adhoc code tend to be performance killers, I doubled the speed of 
mine by de-adhoccing the code (and that although I introduced the 
speed-killer DiffArray)

> 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

If that's not a typo, I'm baffled. My original needed to guess in 5309 
puzzles, and I can't imagine what inference I could have dropped when 
cleaning up the code.

> 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!-)
^^^^^^^^^^^^^^^^^^^^^^^^^^
I'm not sure about that :-)
>
> cheers,
> claus

Cheers back,
Daniel

-- 

"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
	-- Blair P. Houghton



More information about the Haskell-Cafe mailing list