[Haskell-cafe] Code Review: Sudoku solver

[Daniel Fischer]

Am Mittwoch, 5. April 2006 15:09 schrieb Chris Kuklewicz:
> Henning Thielemann wrote:
> > On Mon, 3 Apr 2006, Jared Updike wrote:
> >> or ambiguously) with your Sudoku solver? A rough mesaure of the
> >> difficulty of the unsolved puzzle could be how long the solver took to
> >> solve it (number of steps) (and the number of possible solutions)? Are
> >> puzzles with multiple solutions usually considered harder or easier?
> >> Are these considered proper puzzles?
> >
> > It's an interesting test to run a Sudoku solver on an empty array. :-)
>
> I am cleaning up my old (aka inexperienced) solver based on Knuth's dancing
> links to put on the wiki.  The code is very different than most Haskell
> solutions, since it revolves around a mutable data structure (which is not
> an MArray).
>
> It "solves" an empty array in 81 steps with no backtracking.   It will
> produce a list of all the solutions of an empty board quite efficiently.
>
> Cleaning up my "logic" based solver will take longer.

I've cleaned up my solver, removed a lot of redundant inference steps and made 
the board a DiffArray (is that really faster?).
Now it completely solves (following all guesses) the 36,628 17-hint puzzles in 
about 32 minutes (1909 secs).
It "solves" an empty board in 81 steps without false guesses, but still takes 
over four seconds (that's the price for excessive inference).

I've also written a version using David F. Place's EnumSet instead of [Int],
that takes less MUT time, but more GC time, so is slower on the 36,628 test, 
but faster for a single puzzle.

If anybody feels like improving the code (especially finding better names for 
the functions) and/or placing it on the wiki, I'll be honoured.

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

Cheers,
Daniel

-- 

"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
	-- Blair P. Houghton
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Sudoku.hs
Type: text/x-haskell
Size: 10643 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060407/428e24d8/Sudoku.bin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Check.hs
Type: text/x-haskell
Size: 266 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060407/428e24d8/Check.bin