[Haskell-cafe] Code Review: Sudoku solver

[Daniel Fischer]

Am Montag, 3. April 2006 18:52 schrieb Chris Kuklewicz:
> Claus Reinke wrote:
> >>> > 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..

Exactly, and I wrote a solver with a relatively elaborate strategy last year 
(it was written incrementally, so the code is horrible, I always wanted to 
rewrite it properly but never got to do it, hence I will not post it unless 
asked to), to have both kinds of pleasure, figure out a strategy and teach it 
to my computer.
>
> From a human standpoint, there are some puzzles that are much harder than
> others.  This also applies to the few programs that I have seen.  It is
> this variety of complexity that makes it interesting.
>
> >>> 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?-).
>
> You can go get the 36,628 distict minimal puzzles from
> http://www.csse.uwa.edu.au/~gordon/sudokumin.php that have only 17 clues.
> Then you can run all of them through your program to locate the most evil
> ones, and use them on your associates.  :)

Well, I loaded them down and let my solver determine whether all of them have 
a unique solution (they do), took 76 min 14.260 sec user time, hence roughly 
0.125 secs per puzzle, so I dare say there are no evil ones among them 
(However, Alson Kemp's solver from the HaWiki-page -- which, I don't know 
why, is much faster than Cale Gibbard's -- took over 20 minutes to solve the 
second

0 0 0 0 0 0 0 1 0
4 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0
0 0 0 0 5 0 6 0 4
0 0 8 0 0 0 3 0 0
0 0 1 0 9 0 0 0 0
3 0 0 4 0 0 2 0 0
0 5 0 1 0 0 0 0 0
0 0 0 8 0 7 0 0 0,

so these puzzles may be evil after all).

My solver needed to guess on 5,309 of the 36,628 17-hint puzzles, which I find 
a bit disappointing -- the big disappointment was when neither I nor my 
solver were able to solve the example from the hawiki-page without guessing 
:-( --
does anybody know whether in a uniquly solvable sudoku-puzzle guessing is 
never necessary, i.e. by proper reasoning ('if I put 6 here, then there must 
be a 3 and thus the 4 must go there...' is what I call guessing) there is 
always at least one entry determined?


>
> This also gave me a way to statistically measure if a new deductive step
> made much of a difference (or if it made no difference).  Histograms and
> gnuplot helped.
>
> > [snip Curry language example]
> >
> > 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?-) (*)
>
> I have two versions of a solver.  The first is a re-write of GDANCE bu
> Knuth to solve Sudoku efficiently as a binary cover problem. (see
> http://www-cs-faculty.stanford.edu/~knuth/programs.html )  This uses the
> "Dancing Links algorithm" implemented with STRef's and is very fast.
>
> The second uses a different encoding to look for clever deductions. This
> alone solves some easy problems and comes very close before getting stuck
> on most. There are few though that start with 17 hints and only discover
> one or two more by logic before getting stuck.  These are the most evil of
> all.
>
> You might be interested in the deductions described at
> http://www.sudokusolver.co.uk/
>
> > [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]
>
> I could run ~20,000 puzzles in a couple of hours.  (The collection was
> smaller then).

As stated above, I ran the 36,628 in 76 minutes on a 1200MHz Duron.
But I must confess that my solver takes about 25 secs for the empty puzzle, 
guessing is baaaaaad. 

>
> > 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)?
>
> Did you see the monad at http://haskell.org/hawiki/SudokuSolver ?  Perhaps
> you could generalize that.
>
> > 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.
>
> You need more than 5 examples.  The truly evil puzzles are rarer than that.
>  Go get the set of minimal puzzles and see how far your logic takes you.

Cheers,
Daniel

-- 

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