Re: Sudoku puzzle solver for Apple II

[Scott Hemphill <hemphill@hemphills.net>]

pausch@saaf.se (Paul Schlyter) writes:

> In article <m364i29683.fsf@jade.local>,
> Scott Hemphill  <hemphill@alumni.caltech.edu> wrote:
> 
> > pausch@saaf.se (Paul Schlyter) writes:

[snip]

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

To be fair, some of these programs were explicitly written with the
idea of using the same techniques that humans use to solve the
puzzles, and some use this feature to assign a puzzle difficulty that
is supposed to correspond in some degree to the difficulty a human
would have.

If you are only interested in computer solution, however, and you want
to be able to solve any puzzle, then you have to implement backtracking.
Backtracking is so simple for computers (but painful for humans) that
it makes sense for it to play a major role in computer solution.

[snip]

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

Apparently under 1% slower, and it looks like Michael might put out a
6502 version in the next couple of days.

[snip]

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

Merlin-8.

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