[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Sudoku puzzle solver for Apple II

Anton Treuenfels wrote:

"Michael J. Mahon" <mjmahon@aol.com> wrote in message
oridnYySprSi7CrZnZ2dnUVZ_sadnZ2d@comcast.com">news:oridnYySprSi7CrZnZ2dnUVZ_sadnZ2d@comcast.com...


Anton Treuenfels wrote:


"Michael J. Mahon" <mjmahon@aol.com> wrote in message
GL2dnfZbpopeQyjZnZ2dnUVZ_rKdnZ2d@comcast.com">news:GL2dnfZbpopeQyjZnZ2dnUVZ_rKdnZ2d@comcast.com...



Michael J. Mahon wrote:




It's all good...I'm working on the solver as we "speak".

There's no need to do an OR in the "=9" case, since the only values
that byte can take on are 0 and 1.  So LDA #1; STA (bits),y will do
fine.  This, together with other changes, gets this loop down to 18
cycles per iteration--too bad that it's much less frequent than the
other case.  ;-)



Oh, I gotta stop now...


Please don't!  ;-)




Ah, ya talked me into it...but my next idea is a bit more work...



BTW, as I was thinking about the additional ops in the 65C02, I realized
how much more useful it would have been to provide more symmetry between
the X and Y registers.  For example, the register juggling in the above
loop would be unnecessary if you could post-index by X as well as Y.

Kind of makes you wonder who designed the extensions...



Fred Bowen and friends designed the 65CE02, which had a Z-register that acts
like the Y-registers and 'usurps' the non-indexed indirect instructions of
the 65C02. So

lda (zp)

is really

lda (zp),z

but performs identically to a 65C02 if you never change the Z-register.


Nice.  Another index register is a very powerful addition.


I may add the 65CE02 instructions to my assembler just because I think
they're neat - better than the W65C16S, for instance.



We can avoid this juggling by modifying the addresses of the "neighbor
index" loads, outside the loop.  This allows X to be used directly as
an index.  When combined with storing the index already doubled, it
drops the "<9" loop to 22 cycles per iteration, resulting in a net
saving of about 260 cycles per 'setbox' call.  In our benchmark
puzzle, it's called about 8300 times, for a saving of about 2.3 seconds
out of 30, or 7.6%.  Though I prefer factors of two, I'll take it! ;-)



Self-modifying code?  How about this instead:

    ldx best
    lda bit
    beq set_high_byte_bit:

set_low_byte_bit::

    ldy  other00,x
    lda (bits),y
    ora bit
    sta (bits),y
    ldy  other01,x
    lda (bits),y
    ora bit
    sta (bits),y
    ...                    ; and so on (loop unrolling)
    ldy other19,x
    lda (bits),y
    ora bit
    sta (bits),y
    rts

set_high_byte_bit:

    lda #$01
    ldy other00,x
    iny
    sta (bits),y
    ldy other01,x
    iny
    sta (bits),y
    ...                    ; same unrolled loop
    ldy other19,x
    iny
    sta (bits),y
    rts

>

The key here is that the 'other' table has to be re-arranged (which is where
most of the work involved occurs). Instead of 81 20-byte tables, use 20
81-byte tables. The first table holds the first 'other' cell for all 81
cells, the second table the second, and so on. The 'best' value indexes the
cell we want to find the 'others' of directly, once for each of the 20
tables.


Transposing the array--always an interesting strategy to evaluate
on a 6502.


No address calculation, no counting, no loop overhead, no self-modifying
code - and it's pure 6502 (of course!).


I notice that I have an aversion to self-modifying code, which is
justified in some instances.  But going for speed when all code is
in RAM is not one of those instances.  Code modification is quite
manageable when done in a structured way, and when the modifications
are done orders of magnitude less often than the modified addresses
are used.

BTW, I had no bugs related to the address modification, though I did
find an assembler bug related to incorrectly chosing a zero-page variant
for an instruction with a non-zero page operand of the form "xxx+0*0".

I added a table to multiply an index register by two into the other
index register--4 cycles and doesn't clobber the A reg--no biggie,
but handy in avoiding saves/reloads.

We considered unrolling early in the game, but the space used is pretty
high for the benefit, especially when compared with what can be done
with modified addresses.  I've taken the latter path, in 'select',
'setbox', and the 'bits' save on recursion (not so important), and
got a total speed improvement of a little more than 18%.

Frankly, I'm not sure it was worth the work!

I'll look at the timing of your version of 'setbox'.

I also put the screen painting routine into the solver, and that makes
it much snappier on a 1MHz machine.  And I added a "clear bottom 3
lines" routine so I wouldn't need the 80-column firmware's "clear to
end of screen" control character.

I should have the new version up by Monday, after some more testing.

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