Storing Sudoku Candidates Method

BearClogger · Posted: Wed Nov 23, 2005 7:07 pm Post subject: Storing Sudoku Candidates Method

I was working with creating my own logical solver and I searched the forums for a while but couldn't find anyone using the same storage method. I was storing the candidates in a 9x9 matrix. It's kind of a binary/decimal hybrid. Basically I stored a 9 digit decimal number were each digit was either a 1 or 0 representing the different candidates. So 10110 would have 2,3,5 as candidates. I've come to certain benefits and some drawbacks to storing candidates like this:

Benefits:
-Finding the total number possible places for a candidate in a zone is easy as adding up the numbers in that zone. Since there aren't more than 9 numbers in each zone digits never spill over into the next one.
-Finding naked singles is as easy as seeing if the square root of the candidates number or the number*10 is a whole number. This can only be a whole number if the number has one 1.

Drawbacks:
-Accessing each digit isn't quite as easy as accessing an array. A little parsing of the number is required.
-Doing a logical AND/OR takes a bit of effort as well.
-NOT can be perfomed by int(1/9*10^int(log(A)+1))-A where A is the number the the operation is being performed on. This requires access to an integer truncating function and a log function...

I know there are a few things I'm missing, but has anyone else used this method for storing candidates?

Bo

I also store the cell's candidates as a bitstring in an integer. I use masks to represent each value, e.g. 2 is represented as 0x0002, 3 as 0x0004.
Then the C bitwise operators are used for e.g. accessing a specific value (with and-operation using the mask) removing a specific value (and-operation with inverted bit mask) and so on. Counting the number of candidates is simply done by calculating the number of 1s.
I find this method of storing candidates very efficient.

Bo

BearClogger · Posted: Wed Nov 23, 2005 10:54 pm Post subject:

I was accessing digits like by:

dom · Posted: Thu Nov 24, 2005 9:50 am Post subject:

Like Bo, I've also used base 2 to store the digits in the number. I can see why you might use base 10 as it's more "human" but I think base 2 would work better for you here.

In particular working out how many bits are set doesn't need any counting at all. Just create an array that's 512 big, fill it up with how many bits are set for each index. This is a *very* quick way of testing the number of bits set in a cell. More difficult with decimal digits because you'd have a very sparse and VERY large array, or a hashing system or something. Not as optimal...

And also, bitwise operators are very fast on computers. So to set a bit you just use cellValues |= code[value]; where code[value] is the bitmask for each value that's possible. This is a memory lookup and single instruction on most CPU's where as the decimal version takes far longer to process. (it's still extremely quick, but when you're doing a few billion of them it'll add up)
_________________
Orangeminds Sudoku
http://www.orangeminds.com/sudoku/

BearClogger · Posted: Thu Nov 24, 2005 10:09 pm Post subject:

I know the benefits of binary. I don't think you understood my post. I'm only using a 9x9 array to store all the candidates so it's not a sparse array at all.

dom · Posted: Fri Nov 25, 2005 12:24 pm Post subject:

Sorry, I was unclear in my post. The sparse array I was referring to was specifically concerned with the following optim.

Say you have a 9 digit binary number 10011 and you want to count the bits.

Rather than doing

BearClogger · Posted: Fri Nov 25, 2005 8:39 pm Post subject:

My concerns for my current project are size of the program first, memory usage, and speed last. As of right now my code can find hidden singles and naked singles with using just one 9x9 array and one 3x9 array. For the platform I'm working with, I don't have access to arrays of size 512.

Ruud · Site Admin

The candidates are stored in Sudo Cue as 32-bit integers, of which I'm only using 9 bits to store the candidates.

The resulting integer (ranged 0-511) is the index to an object array, where each instance contains the candidate info for each of these 512 possible values. (Count is one of the properties.)

It is also useful to maintain bit-arrays for remaining candidates within a row/column/box + digit.

Ruud.

dom · Posted: Sat Nov 26, 2005 10:39 pm Post subject:

BearClogger- Sure, well if it makes sense for you to use minimal memory and you're not worried about speed then it sounds like it's a bit of a non-issue. You could probably still save a bit of memory using binary (81x9=729bits) total storage. Or 23 32bit integers, if you're really into getting the memory usage down. Smile

But sure, simple is sometimes best with these things.

Ruud - Yep, there's a lot to be said for these lookup arrays, like you I'm also using them for row/region/column masks to help with rule application. I'm using logical solving rules so there can be quite a lot of scanning for which candidates remain in an area. I've not started using them for digit lookups though. What type of solver is Sudo cue running?

Cheers,
Dom
_________________
Orangeminds Sudoku
http://www.orangeminds.com/sudoku/

Henk · Posted: Sun Nov 27, 2005 7:20 pm Post subject:

In my logical solver, i store the candidates in several different ways. First I have created a cell class, where the candidates are stored as a array. Second i use a optimized bitset, this looks like the origional one but its optimized for speed.

Actually, i store allmost all data of the Sudoku in more ways so i got the bennefit of all. I can use AND and NOT operators as well as quick searching and a nice OO structure. Its a lot of work to get everything synchronized, but it will start to pay back when you begin programming the logic to solve the puzzle.

My generator can generate and rate about 5800 sudoku puzzles each minute on a p4 3000. I think this is pretty fast for a logic solver...

http://c107185.upc-c.chello.nl/Sudoku/index.php