[Haskell-cafe] Code Review: Sudoku solver
Daniel Fischer
daniel.is.fischer at web.de
Mon Apr 3 19:12:11 EDT 2006
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
More information about the Haskell-Cafe
mailing list