Sudoku Programmers :: View topic - Bruteforcing with bits

FAQ

Memberlist

Usergroups

Profile

Bruteforcing with bits

Sudoku Programmers Forum Index -> Solving sudoku

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^(x-1)

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.

ChPicard

Joined: 12 Mar 2008

Posts: 82

Location: Montreal, Canada

Items

Posted: Mon Dec 14, 2009 11:48 pm Post subject: Look BB Sudoku V1.0

Hi Look that, this solver is very fast and bit based solver. http://www.setbb.com/phpbb/viewtopic.php?t=1824&mforum=sudoku Best regards

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 '3-cell integer packing', because it lowers count of operations to be made.

But I'll look that solver for more interesting ideas.

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

What sort of speeds are we talking about? Any chance of re-coding 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.

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

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.

Display posts from previous:

	Sudoku Programmers Forum Index -> Solving sudoku	All times are GMT
Page 1 of 1

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