Introduction
As everyone knows, a Sudoku is a puzzle where the numbers from one to nine must be placed in a 9x9 cells board so that, in each row and column, none of the numbers can be repeated. The board is also divided in nine 3x3 cells sectors, where the numbers cannot be neither repeated. As a clue, some of the numbers are provided initially.
The number of possible combinations is huge, so that, we have to find some kind of optimization in order to discard the maximum possible number of them.
In this article I will show a short and simple algorithm that can solve a Sudoku in less than one millisecond, using bitwise Boolean operations like and and or.
You can find a Spanish version of this article visiting my blog.
This project is written in C# using Visual Studio 2015.
Background
The algorithm is designed so that it only uses data types that are suitable to be placed in the processor cache memory, like int or structs. This is the first optimization.
We want to avoid examine more than one cell to know if a given number can be placed into, so that, some initialization work must be done before starting processing the board, in order to provide in each cell the required information to achieve that.
We can avoid some loops by representing a row using bit positions in a single int, instead of using an array. We have to predefine also bitmasks to quickly check validation conditions.
The decimal system is not well suited to use bitwise operations with numbers, so that we will make a conversion to represent the numbers with only one bit each, in a different position among nine, namely, N = 2n-1, being n = 1,2,...,9.
Done that, we can build a mask for each cell that indicate the allowed numbers. For example, 000010011 allows only the numbers 1, 2 and 5. We can build a mask for the row, other for the column and another one for the sector, and combine all of them to check whether a number can or cannot be placed in a cell.
We will separate the possible positions for each number in nine separate layers, so that we can process them separately. First, a valid combination of 1 will be placed on an empty board. Then, we will pass to try to position a valid combination of 2, limited by the positions occupied by the 1, and so on.
This effectively limits the number of combinations that we have to try. Additionally, once we found the correct position for a number in the first row, it will be never processed again, then, the same with the second row, then the third, and so on, until the first layer has the correct combination of 1, which causes that this layer won't be processed never again. Then, the same process occurs in the second layer, and so on.
The Sudoku initial data must be placed in a text file, with nine rows of nine comma separated numbers, without additional spaces, representing the board. A 0 indicates an empty cell.
The application is a simple dialog box with a New button, which allows select a file to process and shows the results.
Using the code
The board is represented using a 9x9 array of elements of the sCell data type, defined as follows:
private struct sCell
{
public int Value;
public int Row;
public int Col;
public int Sec;
public bool Fixed;
}
private sCell[,] _sudoku = null;
Value is the number contained in the cell, in format 2n-1, or zero if it is empty. Fixed indicates if this cell contains one of the initial values. The other three members, Row, Col and Sec, are bitmasks with the numbers already present in the same row, column and sector as the cell.
We use the SetCell method to initialize a cell with a given number, as well as updating the information of the bitmasks in all the cells on the same row, column and sector:
private void SetCell(int row, int col, int v, bool fix)
{
_sudoku[row, col].Value = v;
_sudoku[row, col].Fixed = fix;
for (int c = 0; c < 9; c++)
{
_sudoku[row, c].Row |= v;
_sudoku[c, col].Col |= v;
_sudoku[(3 * (row / 3)) + (c % 3), (3 * (col / 3)) + (c / 3)].Sec |= v;
}
}
Now, we have to define a working array with 9x9x9 elements to separate all the numbers in nine layers, each one for a different value, where we will store the valid positions using a single bit for each column. For example, if there can be a 1 in the third column, we will use the number 001000000 to indicate that, in the corresponding layer. We will define also masks for the columns and sectors, in order to know in a single operation whether a position is allowed or not. This array contains elements of sNum struct type, defined as follows:
private struct sNum
{
public int Position;
public int Col;
public int ColMask;
public int SecMask;
}
private sNum[,,] _layers = null;
The Position member contains a number with the bit representing the column set to 1. ColMask and SecMask are the bitmasks for the column and the sector. The bitmask for the column is the inverse of the position, we precalculate it to avoid using the not operator in the calculations in the working procedure. The masks of the sectors are 000111111, 111000111 and 111111000 respectively.
In order to avoid process empty positions, we will store the data of the n positions of each row in the first n columns of the array. The Col member is used to store the actual column in the Sudoku board.
The BuildLayers method is called once to perform this initialization work:
private void BuildLayers()
{
int v = 1;
for (int n = 0; n < 9; n++)
{
for (int row = 0; row < 9; row++)
{
int c = 0;
int msec = 0x3F;
int mcol = 0x7EFF;
int bit = 0x100;
for (int col = 0; col < 9; col++)
{
bool set = false;
if (_sudoku[row, col].Fixed)
{
if (_sudoku[row, col].Value == v)
{
set = true;
}
}
else if (((_sudoku[row, col].Row |
_sudoku[row, col].Col |
_sudoku[row, col].Sec) & v) == 0)
{
set = true;
}
if (set)
{
_layers[row, c, n].Position = bit;
_layers[row, c, n].Col = col;
_layers[row, c, n].ColMask = mcol & 0x1FF;
_layers[row, c++, n].SecMask = msec;
}
bit >>= 1;
mcol >>= 1;
mcol |= 0x4000;
if (col == 2)
{
msec = 0x1C7;
}
else if (col == 5)
{
msec = 0x1F8;
}
}
}
v <<= 1;
}
}
The last element we need is an array of nine integers to represent the bitwise positions at each row, an 1 indicating an empty cell and a 0 to indicate a filled one. This can seem counterintuitive, but this way we avoid again the use of the not operator in the working procedure.
_positions = new int[9];
for (int n = 0; n < 9; n++)
{
_positions[n] = 0x1FF;
}
Now, we can start processing all that data. We only have to use a single recursive method divided in two parts, one to continue processing a valid combination and another to try a new one if we are not able to do it. It is the ProcessNextNumber method, which takes a parameter with the number of the layer to process.
private bool ProcessNextNumber(int n)
{
int[] indexes = new int[9];
int[] oldpositions = new int[9];
for (int num = 0; num < 9; num++)
{
oldpositions[num] = _positions[num];
}
int mcol = 0x1FF;
int msec = 0x1FF;
int ix = 0;
int v = 1 << n;
while (true)
{
int index = indexes[ix];
if ((_layers[ix, index, n].Position & msec & mcol & _positions[ix]) != 0)
{
_positions[ix] &= _layers[ix, index, n].ColMask;
_sudoku[ix, _layers[ix, index, n].Col].Value = v;
switch (ix)
{
case 2:
case 5:
mcol &= _layers[ix, index, n].ColMask;
msec = 0x1FF;
ix++;
break;
case 8:
if ((n == 8) || ProcessNextNumber(n + 1))
{
return true;
}
_positions[8] = oldpositions[8];
mcol |= _layers[8, indexes[8], n].Position;
msec = _layers[7, indexes[7], n].SecMask &
_layers[6, indexes[6], n].SecMask;
indexes[8]++;
break;
default:
mcol &= _layers[ix, index, n].ColMask;
msec &= _layers[ix, index, n].SecMask;
ix++;
break;
}
}
else
{
if ((_layers[ix, index, n].Position != 0) && (index < 8))
{
indexes[ix]++;
}
else
{
if (ix == 0)
{
return false;
}
indexes[ix] = 0;
ix--;
_positions[ix] = oldpositions[ix];
mcol |= _layers[ix, indexes[ix], n].Position;
switch (ix % 3)
{
case 0:
msec = 0x1FF;
break;
case 1:
msec = _layers[ix - 1, indexes[ix - 1], n].SecMask;
break;
default:
msec = _layers[ix - 1, indexes[ix - 1], n].SecMask &
_layers[ix - 2, indexes[ix - 2], n].SecMask;
break;
}
indexes[ix]++;
}
}
}
}
The first instructions are to define and initialize the variables. We will use indexes to store the current position in each row of the current combination of values. oldpositions is used to reset the position mask on each row to their initial values. mcol and msec are the masks for the column and sector, we start allowing all the positions to be used. ix is the index of the current row, and v is the number corresponding to the current layer.
To check for the validity of a position, we use the following condition:
if ((_layers[ix, index, n].Position & msec & mcol & _positions[ix]) != 0)
For a valid position, we set to 0 the corresponding bit and we store the value in the _sudoku board:
_positions[ix] &= _layers[ix, index, n].ColMask;
_sudoku[ix, _layers[ix, index, n].Col].Value = v;
Depending on the row we are, the process is different. In the second and fifth row, we are about to change to a new row of sectors, so that the msec mask must be initialized to allow all the positions. The mcol mask accumulates the used columns so that they cannot be used again. Finally the index of the row is incremented to process the next one. We don't need to check anything about the row, as we are placing only one value on each one.
mcol &= _layers[ix, index, n].ColMask;
msec = 0x1FF;
ix++;
In the rest of rows from the first to the eighth, the msec mask accumulates the sector mask of the current row:
mcol &= _layers[ix, index, n].ColMask;
msec &= _layers[ix, index, n].SecMask;
ix++;
When we reach the ninth row, we have a complete combination of values. If we are in the last layer, the process ends, if not, we pass the control to the next layer. If that not succeeds, we have to reset the values of the masks and the positions and try with the next available position in the ninth row.
_positions[8] = oldpositions[8];
mcol |= _layers[8, indexes[8], n].Position;
msec = _layers[7, indexes[7], n].SecMask &
_layers[6, indexes[6], n].SecMask;
indexes[8]++;
On the other hand, if the current position is not valid, we try with the next one, if there is still one available:
if ((_layers[ix, index, n].Position != 0) && (index < 8))
{
indexes[ix]++;
}
If that is not possible, we first check if we are in the first row. That means that there is not a valid combination, and we return the control to the previous layer, indicating it. If we can continue, we reset the index of the current row to 0 to try again all possible positions and we move to the previous row.
if (ix == 0)
{
return false;
}
indexes[ix] = 0;
ix--;
In this row, we have to reset the column and sector mask and the last position used. Finally, we increment the position index to try again.
_positions[ix] = oldpositions[ix];
mcol |= _layers[ix, indexes[ix], n].Position;
switch (ix % 3)
{
case 0:
msec = 0x1FF;
break;
case 1:
msec = _layers[ix - 1, indexes[ix - 1], n].SecMask;
break;
default:
msec = _layers[ix - 1, indexes[ix - 1], n].SecMask &
_layers[ix - 2, indexes[ix - 2], n].SecMask;
break;
}
indexes[ix]++;
The time this algorithm takes to complete is not dependant on the difficulty of the Sudoku (the difficulty for humans, of course), but on the places of the numbers in the final board. So you can find that an easy Sudoku is completed in more time that an extremely difficult one.
And that's all, thanks for reading!!!
