Re: Sudoku puzzle solver for Apple II

["Anton Treuenfels" <atreuenfels@earthlink.net>]

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

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.

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

- Anton Treuenfels