Clever Geek Handbook

Algorithm that Solves Sudoku with Bit Operators

I am studying the algorithm, the point is that it is difficult for me to understand since you are isolating the exact number at the required position without the need (as I see) of an exhaustive search as is customary in this type of algorithm, here's the code:

int trycell(int *x, int pos)
{
    int row = pos / 9;
    int col = pos % 9;
    int i, j, used = 0;

    if (pos == 81)
        return 1;
    if (x[pos])
        return trycell(x, pos + 1);

    for (i = 0; i < 9; i++)
        used |= 1 << (x[i * 9 + col] - 1);

    for (j = 0; j < 9; j++)
        used |= 1 << (x[row * 9 + j] - 1);

    row = row / 3 * 3;
    col = col / 3 * 3;

    for (i = row; i < row + 3; i++)
        for (j = col; j < col + 3; j++)
            used |= 1 << (x[i * 9 + j] - 1);

    for (x[pos] = 1; x[pos] <= 9; x[pos]++, used >>= 1)
    {

        if (!(used & 1) && trycell(x, pos + 1))
            return 1;
    }
    x[pos] = 0;
    return 0;
}
+3


source to share


1 answer


A bitmask containing 9 bits is used, one for each of the numbers. For example, if 100111000 (in binary) is used, this means that somewhere in the cells of the same row / column / sector as the current cell, numbers 9,6,5,4 were set (each bit corresponds to a number with the most the leftmost bit is 9 and the rightmost bit is 1).

The used method is used like this:

used |= 1 << (x[index] - 1);

First, x[index]

it is the content of some cell on the board, which is 0 for an empty cell or 1..9 if the cell is full. Thus, it x[index]-1

is -1 for an empty cell, or 0..8 for a filled cell.

For an empty cell, 1 <-1 is 0. Therefore, it used |= 0;

does not change.



For a filled cell, 1 <(n-1) is a bit in the bitmask. Suppose the filled cell had 5 units in it. Then (1 <4) is equal to 10000 (in binary) or 0x10 (in hex). used |= 0x10

sets this bit to usable (or leaves it set if already set) without affecting other bits. So if 100,000,000 is used in advance, it will be 1,00010,000 afterwards.

So the last part:

for (x[pos] = 1; x[pos] <= 9; x[pos]++, used >>= 1)
{
    if (!(used & 1) && trycell(x, pos + 1))
        return 1;
}

What this loop does:

  • The loop inserts numbers 1..9 into an empty cell one at a time.
  • After inserting a number into a cell, it checks if it indicates used

    that the number was already in the row / col / sector. This is part of !(used & 1)

    the if statement. If the number has already appeared, we will not be able to use that number in this cell, because it will lead to duplication. So this will throw an if error and move on to the next number.
  • If used

    indicated that the number has not yet appeared, it is returned in trycell(x, pos+1)

    . This means that we have filled this cell with a possible number and we want to recursively (and roughly forcefully) move to the next cell to see if there are any possible solutions using this cell with that number.
  • If the call trycell()

    returns 1, then there was a solution, and we can return 1 to indicate that there is a solution (all entries in the panel will be filled at that point). Otherwise we will try the next number.
0


source






More articles:


All Articles