Re: Sudoku puzzle solver for Apple II

[Scott Hemphill <hemphill@hemphills.net>]

dempson@actrix.gen.nz (David Empson) writes:

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

If you think that one's tough, try this one.  It's much harder, at least
for my algorithm.  I don't know where I got it, but I saved it under the
filename "hints17-2".  I have four files of the form "hints17-x", all
very tough, but this one is the worst:

..1.2.7..
.5.....9.
...4.....
.8...5...
.9.......
....6...2
..2......
..6.....5
.....9.83

Hmmm.  I just noticed that there are only 17 givens in this puzzle, which
is the minimum number known to be required.  (What I mean is that although
no one has proved a minimum number, there are no known puzzles with
as few as 16 givens that result in a unique solution.)  That might account
for the "17" in the filename.

Scott
-- 
Scott Hemphill	hemphill@alumni.caltech.edu
"This isn't flying.  This is falling, with style."  -- Buzz Lightyear