My spouse is fond of solving Sudoku’s and so she once came to me and said I should start to solve Sudoku’s to. That would be good training for the brains. O.k. but if I start to solve Sudoku’s, I thought, I want a sustainable solution and that means an algorithm. O.k. this algorithm doesn’t have too much maths behind and my spouse complained that wouldn’t be the idea of doing Sudoku’s. I say: No, it isn’t … it’s pure fun
The rule to solve a Sudoku is quite simple. We have a 9x9 grid. This grid is divided into 9 blocks of 3x3 fields. There some numbers are already given and the empty fields shall be filled by numbers in the way that finally in each row and each column the numbers 1 to 9 occur exactly once and additionally in each block there may occur 1 to 9 exactly once.
If we would intend to solve this Sudoku and start with the 3. element in the 1. row (the field with the “?”), To find out which number is to be put into this element the numbers in the red, green and blue squares must be checked. In all 3 squares the numbers 1 to 9 may occur exactly once. In all 3 squares the numbers 1, 3, 4, 5, 6, 8 and 9 are already there so in this field only the numbers 2 or 7 could be inserted. Now the question is which one should I insert? To answer this, all the other elements must be considered to. That makes things a bit more complex of course
In a computer program this can be solved quite easily.
Some software quality standards say recursive function calls are devil stuff and may not be used. I say that’s nonsense. Some problems can be solved much more elegant using recursive function calls. But they must be applied wisely. Always take care for a clear abort criterion. Otherwise the computer might thank you with a stack overflow.
I implemented my Sudoku solver with a recursive function call and I like that
The algorithm works as follows:
In a recursive function for the first empty element I search for all possible numbers. These numbers I put into a list. Then I try one by one whether this number can be used or not. This I do by temporary inserting the number into to actual field and calling the function recursively for the next empty field. If the number is o.k. the function returns true and if no useful number can be found, the function clears the temporary set number again and returns false. That sounds quite simple. But as the function calls itself recursively this procedure is quite complex and runs through all field several times. For the above sample Sudoku I got 916 recursive calls and the max recursion depth is 81. That’s quite enough.
For the indexing I use the counter actIndex. That gives me an accurate abort criterion, as I know I can abort the recursion if actIndex = 18, and it is quite convenient to jump from one element to the next and address the corresponding element in the 2 dimensional grid.
I defined a basic cell type
public class TBasicCell
{
public int valueSet;
public TextBox tb;
}
It carries its coordinates in the grid, its value which is -1 as long as it is not set and it has a pointer to its text box. O.k. I could use a data grid to display the 9 x 9 Sudoku grid. Then this pointer would not be necessary. But I like the look with the text boxes more.
For one 3 x 3 block I defined the class
public class TBlock
{
public Collection<TBasicCell> cells = new Collection<TBasicCell>();
…}
Which contains 9 elements of the type TBasicCell. One such block is assigned to each element in the Sudoku grid. One such element is of the type
public class TCell : TBasicCell
{
public TBlock block;
}
which is a BasicCell type with the additional block pointer. That carries the information to which block a particular element belongs.To find the possible numbers for a particular element I just gather all set numbers in its row and column and in its block by the function
private List<int> FindPossible(int actX, int actY)
{
int i, k;
List<int> possibleList = new List<int>();
TBlock actBlock;
if (!(field[actX, actY].valueSet > 0))
{
actBlock = field[actX, actY].block;
bool[] impossible = new bool[10] { false, false, false, false, false, false, false, false, false, false };
for (i = 0; i < actBlock.cells.Count; i++) // check for set values in active block
{
if (actBlock.cells[i].valueSet > 0)
{
if (actBlock.cells[i].valueSet <= 9)
{
k = actBlock.cells[i].valueSet;
impossible[k] = true;
}
}
}
for (i = 0; i < 9; i++) // check for set values in active row
{
if (field[actX, i].valueSet > 0)
{
if (field[actX, i].valueSet <= 9)
impossible[field[actX, i].valueSet] = true;
}
}
for (i = 0; i < 9; i++) // check for set values in active col
{
if (field[i, actY].valueSet > 0)
{
if (field[i, actY].valueSet <= 9)
impossible[field[i, actY].valueSet] = true;
}
}
// now we have all impossible values for the actual Cell
if (field[actX, actY].valueSet < 0)
{
for (i = 1; i <= 9; i++)
{
if (!impossible[i])
possibleList.Add(i);
}
}
}
return possibleList;
}
This function uses the array impossible which basically represents the numbers 1 o 9 in its indexes and if one of these numbers is set, the corresponding index in the array is set to true. At the end of the function I just run though this array and for all indexes that are not true I add the corresponding number to the list possibleList and return this list.
The recursive function to determine the correct number to be set in one particular element is:
private bool FillCell(int actIndex)
{
int i;
bool result = true;
bool foundOne = false;
int nextX = -1;
int nextY = -1;
if (actIndex < 81)
{
while ((!foundOne) && (actIndex < 80))
{
actIndex++;
nextX = actIndex % 9;
nextY = actIndex / 9;
foundOne = (field[nextX, nextY].valueSet == -1);
}
foundOne = false;
if ((nextX >= 0) && (nextY >= 0))
{
if (field[nextX, nextY].valueSet == -1)
{
List<int> list = FindPossible(nextX, nextY);
if (list.Count > 0)
{
for (i = 0; i < list.Count; i++)
{
field[nextX, nextY].valueSet = list.ElementAt(i);
if (FillCell(actIndex))
{
i = list.Count;
foundOne = true;
}
}
if (!foundOne)
{
field[nextX, nextY].valueSet = -1;
result = false;
}
}
else
{
result = false;
}
}
else
{
result = true;
}
}
}
else
result = true;
return result;
}
This function gets the actual index as a number between -1 and 81 and first tries to find the next not set element. If it finds one it calls FindPossible to get all possible numbers for this element. With these numbers one by one it calls itself recursively with the next index. At the end of the recursion, when actIndex = 81 the last element has been set, it returns true to signalize that the Sudoku is solved. With this true as return value the recursion goes upward till it reaches its start and ends. If the Sudoku could not be solved by some reason the return value will be false.
The only thing that is left: The algorithm does not like if anybody enters twice the same number. Therefore that must be checked in advance and this is done by the function CheckPossible() which is almost the same as FindPossible(int actX, int actY). If this function returns true we can start the function FillCell with the start index = -1 and it returns true, the Sudoku is solved
After a while I extended the C# demo project in order to deal with free form Sudoku’s to. So there are two modes implemented in the demo project:
The standard form Sudoku:
The free form Sudoku:
The description how to do a free form Sudoku is a bit too much to be written on this page. So I decided to write a little manual and include it in the project.
Additionally there is an executable of the Sudoku Solver for downloading including the manual. To use it, download the SudokuBin.zip, unpack it and execute the Sudoku.exe application.
I implemented an online Sudoku solver and it can be found here
It runs on Android version 4.4 and higher and I’m not sure whether it looks correct on all sizes of screens or not as I just implemented one visual design and scale it at program start. At least on my phone it looks quite nice.
It can be downloaded here:
