Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

grid candidate record

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
leeo

Joined: 24 Jun 2009
Posts: 6
:
Location: USA NW

Items
PostPosted: Wed Aug 26, 2009 12:40 pm    Post subject: grid candidate record Reply with quote

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
Back to top
View user's profile Send private message
dmhayden

Joined: 01 Aug 2007
Posts: 16
:
Location: Central New Jersey

Items
PostPosted: Sat Oct 10, 2009 12:28 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message AIM Address
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron