Re: Sudoku puzzle solver for Apple II

[dempson@actrix.gen.nz (David Empson)]

Scott Hemphill <hemphill@hemphills.net> wrote:

> pausch@saaf.se (Paul Schlyter) writes:
> 
> > In article <XtudnVI15qUVVCnZnZ2dnUVZ_oydnZ2d@comcast.com>,
> > Michael J. Mahon <mjmahon@aol.com> wrote:
> > >It is amazingly fast!  Most Sudoku solvers run on modern PCs thousands
> > >of times faster than a 1MHz Apple II, and take seconds to solve a
> > >puzzle,
> > 
> > I don't believe that!  Check out this Sudoku solver:
> >     http://homepage.ntlworld.com/valleyway/solver.html
> 
> I don't know about _most_ Sudoku solvers, but there are a lot of slow ones
> out there.  And in terms of taking seconds, I think Michael was talking
> about difficult puzzles, not easy ones.  Our most frequently used test
> puzzle was one we called "evil01".  I loaded this into the solver you
> mentioned and it took about 4 seconds on my 3GHz machine.  Here's the
> puzzle:
> 
> .2.......
> ...6....3
> .74.8....
> .....3..2
> .8..4..1.
> 6..5.....
> ....1.78.
> 5....9...
> .......4.

That's certainly a tough one. I regularly do the puzzles in the local
paper, and this one took me about 1h10m, which is twice as long as the
typical time I take for a "diabolical" puzzle.

Only one speculative move and backtrack required, but I had to stretch
my usual techniques somewhat to avoid guesswork near the beginning.

The Sudoku program on my PDA took about ten seconds to verify it was
solvable (it usually takes well under a second).

-- 
David Empson
dempson@actrix.gen.nz