Re: Sudoku puzzle solver for Apple II

[Scott Hemphill <hemphill@hemphills.net>]

pausch@saaf.se (Paul Schlyter) writes:

> In article <XtudnVI15qUVVCnZnZ2dnUVZ_oydnZ2d@comcast.com>,
> Michael J. Mahon <mjmahon@aol.com> wrote:
> >Scott Hemphill and I recently collaborated to create a Sudoku puzzle
> >solver for Apple II computers.  The machine language solver is Scott's,
> >with some adaptations by me, and I wrote the interactive Applesoft
> >front-end.
> >
> >SUDOKU runs on any Apple II with 80-column firmware and a 65C02
> >processor, which includes the IIc, the IIc+, the Enhanced //e, and
> >the IIgs.
> >
> >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.

> It's written in Javascript, which of course is a quite inefficient
> programming language - yet it needs less than half a second to solve
> a sudoku, on a 4+ year old PC running at a moderate 1.8 GHz clock speed.

I don't know how inefficient Javascript is.  Is this a good speed?  My
C program solves the evil01 puzzle in about 2 milliseconds.

> You must have encountered some really sloppily written sudoku solvers
> for the PC if they required several seconds to solve a sudoku....

Yup, if by sloppy you mean not choosing the most efficient algorithms.

> > but Scott's solver is so time and space efficient that it
> >solves puzzles in seconds *running on an Apple II*!
> >
> >Check it out at:
> >
> >http://members.aol.com/mjmahon/Sudoku.html
> >
> >It is available both as a ShrinkIt disk archive and as a .dsk image.
> 
> ...but why does it require a 65C02 ?  Couldn't it have been written
> in plain 6502 assembly language?

It requires a 65C02 because that's the way I initially wrote the
assembly language solver.  As it underwent various transformations
I started migrating it towards the 6502, but we decided to keep the
speed and release the code.  It's public domain, with all sources
provided, so anyone is free to modify it for the 6502.  Furthermore,
we didn't put in all the speed tweaks we thought of, and Michael has
thoughtfully mentioned some of those improvements on his website if
anyone wants to pick up where we left off.

> >Enjoy!
> >
> >(BTW, the execution profile referred to in the paper has not yet
> >been uploaded, so for the time being, that's a 404. ;-)

(I've sent it to Michael, so I imagine it will appear there soon.)

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