Re: Sudoku puzzle solver for Apple II

[pausch@saaf.se (Paul Schlyter)]

In article <m364i29683.fsf@jade.local>,
Scott Hemphill  <hemphill@alumni.caltech.edu> wrote:

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

:-) ....this shows the importance of carefully specifying the initial conditions
in your benchmark.  I just typed in some numbers until I got a unique solution,
and used that as a test case.

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

That's indeed part of sloppiness!

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

APproximately how much slower do you think a 6502 version would have
been?  10% slower?  Twice as slow?  10 times as slow?

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

What assembler did you use?
 
>>>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

-- 
----------------------------------------------------------------
Paul Schlyter,  Grev Turegatan 40,  SE-114 38 Stockholm,  SWEDEN
e-mail:  pausch at stockholm dot bostream dot se
WWW:     http://stjarnhimlen.se/