[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Sudoku puzzle solver for Apple II
BLuRry wrote:
BTW, animating this screen in HGR or DHR would have big speed effects!
Yeah, I know. I remember some of the good ol' softdisk programs being
a big sluggish. But if optimized (e.g. only update the characters that
have actually changed) it wouldn't be all that unbearable.
No, it would still be unbearable.
The animation that SUDOKU does is not 15fps or 30fps. It's doing
about 525 screen updates per second! And if you skip any of them,
you have to look at all 81 digits, because you don't know which ones
have changed! So anything you hope to make up in the straightaway
you will lose in the curves. ;-)
This is a problem that hardware character generators were invented
to solve, and every Apple II has one of its very own. ;-)
Every 'setbox' and 'unsetbox' places and removes a digit from the
screen memory, and each such operation requires 37 cycles. All but
9 of those are spent just getting the screen address to update, and
only 9 are spent changing the screen memory. If you have to update
7-8 bytes of HGR memory, or 14-16 bytes of DHR memory, with a pattern
that will take over a dozen cycles to set up addressing for, things
will get s-l-o-w-e-r.
(BTW, an accelerator doesn't help as much as you'd like, since all
the screen stores have to run at 1MHz.)
Um, editing the puzzle after solution has started can't be done.
You have to re-start the solver.
I meant more along the lines of this: http://www.websudoku.com/
(the original provided numbers of the puzzle are not editable, sort of
a way to prevent you from shooting your own feet.)
Ah. I suppose this could be useful for experimentation with a puzzle.
I never thought of the program as a "paper" for solving puzzles by
hand, only as a machine solver... To be used as a "coach", a very
different interface and "coaching" functions would be appropriate.
You might want to write such a program. ;-)
It wouldn't be too hard to add uneditable boxes to the BASIC program,
just use a different representation for the "givens", like inverse text
(though it looks a little sloppy in the grid, since inverse digits tend
to merge with the major dividing "lines"). And the solver would have to
ignore that distinction by masking the grid entries--no problem.
Have at it! But you might want to wait a couple of days to let me
get a new version re-converged.
Frankly, I personally don't have much interest in making this program
more like some other program--as I'm sure you can understand. ;-)
Think of this program more like a "prover"--it tells you whether a
puzzle is inconsistent, has a unique solution, or has many solutions--
but it doesn't help you design puzzles or decide what to do next.
-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."