
View previous topic :: View next topic 
Author 
Message 
 egon
 Joined: 14 Dec 2009  Posts: 3  :   Items 

Posted: Mon Dec 14, 2009 10:50 pm Post subject: Bruteforcing with bits 


Here's a quick way of doing bruteforce solving with bit fiddling.
First we're I'm showing the simple version...
Code: 
First of all we encode each cell as following
0 (dec) => 000000000 (bin)
1 (dec) => 000000001 (bin)
2 (dec) => 000000010 (bin)
3 (dec) => 000000100 (bin)
...
basically
x => 2^(x1)

Next we define a function BitCount (also known as PopulationCount)
that counts how many bits are in an integer. Probably the best way is
to do a lookup table for it.
So basically we have got a board b with dimensions 9x9.
Now to check whether there's a clash in a group (row, column, box).
Code: 
an example checking the row 'y':
row = b[0,y]  b[1,y]  b[2,y]  b[3,y]  b[4,y]  b[5,y]  ...  b[8,y]; //  is bitwise 'or' operation
rowc = BitCount(b[0,y]) + BitCount(b[1,y]) + BitCount(b[2,y]) + ... + BitCount(b[8,y]);
isclashing = BitCount(row) != rowc;

Here's why it works.
We can ignore 0 valued cells (because '0 or x == x', 'PopCount(0) = 0' ).
If there's a clashing then there must exist such value x, that occurs in
two cells. That means we get 'PopCount(x) + PopCount(x) == 2' and 'PopCount(x or x) == 1'.
It's easy to see that if there are no clashes then 'BitCount(row)' and 'rowc' must be equal.
Now to make this idea faster we're going to make another table 'e' with
dimensions 3x9, as following:
Code: 
e[x,y] = (b[x*3, y] <<< 18)  (b[x*3 + 1, y] <<< 9)  b[x*3 + 2,y] // <<<is>> 18)  (row >> 9)  row) & MASK_CELL; // MASK_CELL is a constant 111111111 (bin)
isclashing = PopCount(row) != rowc;

We can use this type of checking similarly in columns and boxes.
Here's my code for it in delphi:
Code: 
function BoardValid(const Board: TSudokuBoard): Boolean;
var
x, y , col, box, colc, boxc, row, rowc: Cardinal;
begin
// check columns and boxes
for x:= 0 to 2 do
begin
// first iteration
box := Board[x,0] or Board[x,1] or Board[x,2];
boxc := PopCount(Board[x,0]) + PopCount(Board[x,1]) + PopCount(Board[x,2]);
col := box;
colc := boxc;
box := OrCellInteger(box);
Result := PopCount(box) = boxc;
if not Result then exit;
// second iteration
box := Board[x,3] or Board[x,4] or Board[x,5];
boxc := PopCount(Board[x,3]) + PopCount(Board[x,4]) + PopCount(Board[x,5]);
col := col or box;
colc := colc + boxc;
box := OrCellInteger(box);
Result := PopCount(box) = boxc;
if not Result then exit;
// third iteration
box := Board[x,6] or Board[x,7] or Board[x,8];
boxc := PopCount(Board[x,6]) + PopCount(Board[x,7]) + PopCount(Board[x,8]);
col := col or box;
colc := colc + boxc;
box := OrCellInteger(box);
Result := PopCount(box) = boxc;
if not Result then exit;
Result := PopCount(col) = colc;
if not Result then exit;
end;
for y:= 0 to 8 do
begin
rowc := PopCount(Board[0,y]) + PopCount(Board[1,y]) + PopCount(Board[2,y]);
row := Board[0,y] or Board[1,y] or Board[2,y];
row := OrCellInteger(row);
Result := PopCount(row);
if not Result then exit;
end;
end;

We can use this method also for getting candidates values for a cell.
Values that are not yet in the box, row or column.
Let's say x = 2, y = 4 (9x9 board coordinates). We'll or
together all cells in the row and box. Then move all the cell positions
in the integer to the desired cell. Then we or in all the row values.
And finally extract the negative of the cell.
Code: 
c = e[0,4]  e[1,4]  e[2,4]  e[0,3]  e[0,5];
c = (c >>> 9)  (c >> 18)  c;
c = c  e[0,0]  e[0,1]  e[0,2]  e[0,6]  e[0,7]  e[0,8];
c = !c & MASK_CELL; // MASK_CELL = 111111111 (binary)

Now in integer 'c' all candidate values are set. That means '101001000' would
mean the possible values for that cell are 4, 7, 9.
Hope this helps someone. Or someone can build on it and make it faster.
I've not finished yet my solver, but when I do I'll update. 

Back to top 


 ChPicard
 Joined: 12 Mar 2008  Posts: 82  :  Location: Montreal, Canada  Items 


Back to top 


 egon
 Joined: 14 Dec 2009  Posts: 3  :   Items 

Posted: Tue Dec 15, 2009 6:52 am Post subject: Re: Look BB Sudoku V1.0 


ChPicard wrote:  Hi
Look that, this solver is very fast and bit based solver.
***
Best regards 
Didn't know about that. Yeah, it has got some similar aspects, but not quite same (still interesting though).
Speedup for my method comes from the '3cell integer packing', because it lowers count of operations to be made.
But I'll look that solver for more interesting ideas. 

Back to top 


 sudoking
 Joined: 20 Oct 2009  Posts: 40  :   Items 

Posted: Tue Dec 15, 2009 8:50 am Post subject: Re: Look BB Sudoku V1.0 


egon wrote:  ChPicard wrote:  Hi
Look that, this solver is very fast and bit based solver.
***
Best regards 
Didn't know about that. Yeah, it has got some similar aspects, but not quite same (still interesting though).
Speedup for my method comes from the '3cell integer packing', because it lowers count of operations to be made.
But I'll look that solver for more interesting ideas. 
What sort of speeds are we talking about? Any chance of recoding your solver in C, instead of (what language is that anyway), so a direct comparison can be made? I'd be mightily impressed if your solver is faster than Brian's. His is faster than anything else I've ever seen. 

Back to top 


 egon
 Joined: 14 Dec 2009  Posts: 3  :   Items 

Posted: Tue Dec 15, 2009 9:47 am Post subject: Re: Look BB Sudoku V1.0 


sudoking wrote:  egon wrote:  ChPicard wrote:  Hi
Look that, this solver is very fast and bit based solver.
***
Best regards 
Didn't know about that. Yeah, it has got some similar aspects, but not quite same (still interesting though).
Speedup for my method comes from the '3cell integer packing', because it lowers count of operations to be made.
But I'll look that solver for more interesting ideas. 
What sort of speeds are we talking about? Any chance of recoding your solver in C, instead of (what language is that anyway), so a direct comparison can be made? I'd be mightily impressed if your solver is faster than Brian's. His is faster than anything else I've ever seen. 
Only test I've only made this far is checking validity of the board (using almost the same code as shown in the post). It tested 1,000,000 valid boards in 0.4s. But it really doesn't give much info as there's no comparison data.
I'm not saying it will be faster. That I have yet to test.
Brian's solver uses caching for groups so that might give him an edge.
I thought my solver more of an educational type. Using one integer for multiple computation. (Similar to BitCount where you use gradual shifting and masking to get fast answer.)
And, I'm writing it in delphi. So it will be probably compilable by Lazarus (free pascal). But when I've got time I'll write it in C. 

Back to top 




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

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
