grid candidate record

leeo · Posted: Wed Aug 26, 2009 12:40 pm Post subject: grid candidate record

I'm starting again from foundations. The candidate list for each cell can be described by a two-byte value (ushort in many languages). This is a possible layout:

gcr // grid candidate record

bit0 == 1 ~ value is a given (or initial value)
bit1 == 1 ~ 1 is a candidate for this cell
bit2 == 1 ~ 2 is a candidate for this cell
bit3 == 1 ~ 3 is a candidate for this cell
...
bit9 == 1 ~ 9 is a candidate for this cell
bitA == 1 ~ a single candidate value remains
bitB == 1 ~ single value has been propogated to all "toching" cells.
bitC == 1 ~ value is speculated (or a guess)
bitD == 1 ~ valud is affected by a speculated value elsewhere
bitE unused
bitF == 1 ~ contradiction detected, no candidates are valid for this cell

and I've started with these operations on a gcr - grid candidate record

FromGiven( in ch : char ) // assign gcr to be given with value _ch_
FromString( in s : string ) // assign gcr to be the candidates _s_
ToString() : string // return the candidate list for this cell
elim( in e : byte ) // remove e as a candidate, if cell has e as a candidate

union( params gcr[] others ) : gcr
innersection( params gcr[] others ) : gcr

dmhayden · Posted: Sat Oct 10, 2009 12:28 am Post subject:

I took a much simpler approach on the theory that memory is cheap.

Each square has two attributes: the fixed value (or zero if the value isn't known yet), and a bitmap of the possible values that this square can take. I don't store an indication of whether a value has propagated to the neighbors because when I set the value, I just propagate it immediately.

When it comes to doing speculative work, I create a new board that represents the speculation.

I guess it all depends on your philosophy. My goal in writing my solver was both clarity and efficiency, but when those two conflicted, I chose clarity over efficiency. Of course "clear" is entirely subjective.

Dave