Solving a Sudoku as an optimization problem

Solving any Sudoku is a problem that can seem complicated if brute force methods are used, testing each and every one of the possible combinations. But, with the right approach, any of these problems can be solved in a few milliseconds. In this article, I will show you a way to achieve it through an optimized method.

In this link you can download the source code of the program to solve sudokus, written in csharp with Visual Studio 2015.

To enter the data in the program easily, you have to create a text file with the numbers of the cells separated by commas, a row in each line of the file, with a zero for the empty cells and the corresponding number for the fixed ones, without adding additional spaces.

The program is a simple dialog box with a New button that will allow us to select the desired file and then present the solved Sudoku, with the fixed numbers colored in red and the rest in black:

Let’s see how to propound this problem so that we can reduce the number of operations to be performed and optimize the process to find the solution in the shortest possible time.

As everyone knows, a Sudoku is a board of 9x9 squares in which the numbers from 1 to 9 must be placed, so that each row and column contains all of them without repetition. The board is divided into 9 sectors of 3x3 squares that must also contain all these numbers. As an initial clue, a few fixed cells are provided as part of the final solution.

The simplest algorithm to solve this problem is pure brute force. Test all the possible values in each of the boxes until you find a solution, but that system can take several minutes, since the number of possibilities is very high, so let's do some work to find a more intelligent approach that minimizes all those possibilities.

The first optimization will be a generic one. Simple data types, such as int or bool, in addition to the struct types, are candidates to be stored in the processor's cache, unlike classes, which are objects that are stored as references in normal RAM, which access time is high in comparison. So, all the data that we are going to use will be defined taken that into account.

The natural numbers in decimal notation are also not appropriate, since we need up to three bits to represent the values from 1 to 9. But we can represent them using a single bit in a different position for each of them, transforming them with the operation N = 2^n-1, to be able to work with them easily using logical operations such as and and or. Since we have nine numbers, we will use nine different bits to represent them:

1 = 000000001
2 = 000000010
3 = 000000100
4 = 000001000
…
9 = 100000000

To represent each cell of the board, we will use a struct that will contain a combination of these bits to indicate the possible allowed values, so that we do not have to go inspecting all the squares of the row, the column and the sector to know what values we can place in a cell:

private struct sCell
{
public int Value;
public int Row;
public int Col;
public int Sec;
public bool Fixed;
}

The Value member will contain the current value of the cell or zero if it is empty. Row will contain the combination of bits of all the numbers present in the row, Col those in the column and Sec is for the sector, while Fixed will indicate if it is a fixed value. To represent the board we will create the _sudoku array of 9x9 elements of this type. With SetCell we will set the value of a box and fill in the data of all the boxes in the row, column and sector to indicate the values that are already present and, therefore, we cannot repeat them again:

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;
}
}

This function will be used to initialize the board with the fixed values that we will read from the data file. Once this is done, to know if a certain value v can go in a certain cell, we just have to check the following logical operation:

(_sudoku[row, col].Row |
_sudoku[row, col].Col |
_sudoku[row, col].Sec) & v) == 0

But checking cell by cell of the board is not the best way to quickly solve the problem, so we will build another working array that will contain all possible combinations of all numbers. It is the _matrix array, of 9x9x9 elements. The first two dimensions are for the rows and columns, the third one is for each one of the nine values that the cells of the board can take. Each position contains the following struct:

private struct sNum
{
public int Value;
public int Col;
public int ColMask;
public int SecMask;
}

Here, Value contains a binary number that uses 9 bits to indicate the position of the cell within the corresponding row of the board. For example, the third cell is indicated with the value 001000000. Instead of storing the data in the corresponding column of the board for each row, we will do it continuously from the first position. Thus, if in the first row there may be three positions that contain, for example, a value of 1, for example in the second, fourth and eighth cells, we will use the first three positions to indicate this, and in the Col member we will indicate the actual column in which the data are found. In this way, it is not necessary to process all the cells of each row, but only the first ones until finding one with a Value of zero.

The ColMask and SecMask members contain auxiliary data to check whether the given value has already been set in the column and in the sector. For example, for the second cell in the first row, ColMask will contain 101111111 and SecMask 000111111. These values will be used to determine if we can place or not a certain number in a cell on the board.

With BuildMatrix we will build this array from the data contained in the _sudoku array:

private void BuildMatrix()
{
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++)
{
if (_sudoku[row, col].Fixed)
{
if (_sudoku[row, col].Value == v)
{
_matrix[row, c, n].Value = bit;
_matrix[row, c, n].Col = col;
_matrix[row, c, n].ColMask = mcol & 0x1FF;
_matrix[row, c++, n].SecMask = msec;
}
}
else if (((_sudoku[row, col].Row |
_sudoku[row, col].Col |
_sudoku[row, col].Sec) & v) == 0)
{
_matrix[row, c, n].Value = bit;
_matrix[row, c, n].Col = col;
_matrix[row, c, n].ColMask = mcol & 0x1FF;
_matrix[row, c++, n].SecMask = msec;
}
bit >>= 1;
mcol >>= 1;
mcol |= 0x4000;
if (col == 2)
{
msec = 0x1C7;
}
else if (col == 5)
{
msec = 0x1F8;
}
}
}
v <<= 1;
}
}

Now we have all the necessary data to start solving the Sudoku. We will use a third array of integers, _numbers, to mark the bits of the cell positions in which we have already placed a number, so that we do not try to place a different one in the cells marked.

The procedure is very simple, we will start placing in each row a single 1 until we have all the rows completed, then we will place the 2, also one in each row, and so on until 9. We will try all the possible combinations until the board is complete. If we find that we cannot complete a level for one of the numbers, we will return to the previous level to try the next combination.

The advantage of this system is that each level limits the possible combinations that can occur in the next level, since we cannot place a number in an occupied cell. When in the first row we have put the value in the correct position, we will no longer process it again. Same thing will happen with the second one, the third one, etc. Nor will we re-process a level once we have put all the values in the correct position, so that, with each number, the possible combinations to check in the next level reduces significantly. This is performed by the ProcessNextNumber method, to which we pass as a parameter the number, or level, to be processed, starting with the 0, corresponding to the 1 value.

The first thing to do is a variable initialization work for the current level:

int[] indexes = new int[9];
int[] oldnumbers = new int[9];
for (int num = 0; num < 9; num++)
{
oldnumbers[num] = _numbers[num];
}
int mcol = 0x1FF;
int msec = 0x1FF;
int ix = 0;
int v = 1 << n;

We use indexes to indicate, for each row, the index of the _matrix array that we are using to test the current combination of values. oldnumbers contains the initial values, for each row, of the _numbers array, so that we can reset these values to test a new combination. mcol is a mask of bits to know which columns we have already set, and msec is a mask for the sectors. ix contains the index of the row that we are processing, and v is the value of the number corresponding to the level, in the 2^n-1 format.

The working loop has two parts, depending on whether we can place a new value in the current row or not. If we can place a new value, the following code is executed:

if ((index < 9) &&
((_matrix[ix, index, n].Value & msec & mcol & ~_numbers[ix]) != 0))
{
_numbers[ix] |= _matrix[ix, index, n].Value;
_sudoku[ix, _matrix[ix, index, n].Col].Value = v;
mcol &= _matrix[ix, index, n].ColMask;
if ((ix == 2) || (ix == 5))
{
msec = 0x1FF;
}
else
{
msec &= _matrix[ix, index, n].SecMask;
}
ix++;
if (ix == 9)
{
if (n == 8)
{
return true;
}
if (ProcessNextNumber(n + 1))
{
return true;
}
ix = 8;
_numbers[8] = oldnumbers[8];
mcol |= (~_matrix[8, indexes[8], n].ColMask) & 0x1FF;
msec = _matrix[7, indexes[7], n].SecMask &
_matrix[6, indexes[6], n].SecMask;
indexes[8]++;
}
}

We start by marking, in the _numbers array, the position that we have placed. We also put the number on the _sudoku board. We eliminate the corresponding column bit in the mcol mask, and we do the same thing with the msec sector mask, taking into account that it is necessary to re-initialize it every time we move to a new sector of rows. We increase the row index and, if we have reached the last one, we check if we are placing the number 9, in which case we have finished the Sudoku, or we process the next level.

If it is not possible to finish the next level, the combination of values of the current level is incorrect, so we try the next position in row 9. We also reset the values and the masks.

If it is not possible to place a number in the current row, the following code is executed:

if ((index < 9) && (_matrix[ix, index, n].Value != 0))
{
indexes[ix]++;
}
else
{
if (ix == 0)
{
return false;
}
indexes[ix] = 0;
ix--;
_numbers[ix] = oldnumbers[ix];
mcol |= (~_matrix[ix, indexes[ix], n].ColMask) & 0x1FF;
switch (ix % 3)
{
case 0:
msec = 0x1FF;
break;
case 1:
msec = _matrix[ix - 1, indexes[ix - 1], n].SecMask;
break;
default:
msec = _matrix[ix - 1, indexes[ix - 1], n].SecMask &
_matrix[ix - 2, indexes[ix - 2], n].SecMask;
break;
}
indexes[ix]++;
}

If we have not yet tested all the positions in the row, we move on to the next one. In another case, we check if we are in the first row, which means that the combination is impossible, and we return control to the previous level. Otherwise, we go back to the previous row and try the next cell, resetting the value of the row positions and the column and sector masks.

With this procedure, we can solve any valid Sudoku in a few milliseconds. The time it takes for the algorithm does not depend on the difficulty of the Sudoku, but rather on the time it takes to get the correct combinations for each level of numbers, so that it is possible to solve a Sudoku of extreme difficulty in less time that an easy one.