[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Sudoku puzzle solver for Apple II
Paul Schlyter wrote:
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
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.
You must have encountered some really sloppily written sudoku solvers
for the PC if they required several seconds to solve a sudoku....
That may be--I haven't actually tried a bunch of PC Sudoku solvers.
If they are also "tidy" enough, perhaps one of these faster (and
hopefully small) solvers could also have been ported to the Apple II.
I probably should have been satisfied simply to say that it's fast. ;-)
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?
I usually enforce that restriction on my own code, and am seldom much
constrained by it. However, in this case, a few 65C02 instructions
relieve register pressure in inner loops, making a quite measurable
difference in performance (but still less than a factor of 2, so a
6502 version is quite practical).
I had it on my list to do a 6502 version, but thought it would be
interesting to get this version out for people to play with.
Note that it also depends on the 80-column firmware control characters,
so that pretty well pushes users toward 65C02 machines. The only one
that is "popular" and left out is the unenhanced //e. ;-(
Enjoy!
(BTW, the execution profile referred to in the paper has not yet
been uploaded, so for the time being, that's a 404. ;-)
This has now been uploaded, so the profile is there. ;-)
-michael
Fast Sudoku solver for Apple II's!
Home page: http://members.aol.com/MJMahon/
"The wastebasket is our most important design
tool--and it's seriously underused."