Introduction
After solving several Sudoku problems from newspapers and magazines, I started thinking about the algorithm one would use to solve these puzzles on the computer.
Background
The premise is very straightforward: starting with a partially filled in grid, the remaining blank cells must be filled in so that every row, every column, and every 3x3 box contains the digits 1 through 9. The source code attached includes the project that when run will generate a default 9x9 grid and accepts user input of the known cells. After filling in the cells, clicking "Calculate" will start the computation, and if one is found, it is displayed.
In addition to the standard 9x9 grids that have the unique property of 3x3 subgroups that must also contain the digits 1 through 9, I wanted to devise an algorithm that was generic enough to handle a grid of any size. These custom grids, if they are of a size that is a perfect square (1, 4, 9, 16, etc.), will compute a subgroup property for grids of the size of the square (1, 2, 3, 4, etc.). So in a 16x16 grid, each 4x4 subgrid must contain the digits 1 through 16, in addition to the requirement that these digits be present in every row and column of the main grid. Any grid that is not sized based on a perfect square will only compute a solution based on the rows and columns.
To facilitate testing grids that are of sizes besides 9x9, the included application supports the creation of a custom sized grid, capable of solving any size "Doku" problem.
Using the Code
The code is broken into two classes, DukuForm
, which is the user interface for this application, and DukuGrid
, which is the class that contains the doku computation algorithm. The code is written for .NET 2.0, though no new types were leveraged, so it should be fairly straightforward to get this to run in 1.1.
Compute Method
This is the method that does most of the work. Regardless of the size of the grid that the DukuGrid
class was created with, if this method is called with 0,0 as starting parameters, the entire grid will be recursively computed. The additional parameter, which should only ever be set to true
in the case that the grid was based on a perfect square dimension, will determine whether the grid enforces the additional constraint of having to detect the smaller subgrids.
public bool Compute(int row, int col, bool applyPerfectSquares)
{
int nNextRow = row;
int nNextCol = col;
bool isLastCell = !NextRowCol(ref nNextRow, ref nNextCol);
if (statusGrid[row][col] == DukuStatus.LOCKED)
{
if (isLastCell)
return true;
return Compute(nNextRow, nNextCol, applyPerfectSquares);
}
ArrayList possibilities = new ArrayList(nRowsColumns);
for (int val = 1; val <= nRowsColumns; val++)
{
bool bFound = false;
for (int rowIdx = 0; (rowIdx < nRowsColumns) &&
(!bFound); rowIdx++)
{
if (numericGrid[rowIdx][col] == val)
{
bFound = true;
}
}
for (int colIdx = 0; (colIdx < nRowsColumns) &&
(!bFound); colIdx++)
{
if (numericGrid[row][colIdx] == val)
{
bFound = true;
}
}
if (applyPerfectSquares)
{
int subGridRowMax =
(nSubGridSize * ((row / nSubGridSize) + 1)) - 1;
int subGridColMax =
(nSubGridSize * ((col / nSubGridSize) + 1)) - 1;
for (int x = subGridRowMax - (nSubGridSize - 1);
x <= subGridRowMax; x++)
for (int y = subGridColMax - (nSubGridSize - 1);
y <= subGridColMax; y++)
if(numericGrid[x][y] == val)
bFound = true;
}
if (!bFound)
possibilities.Add(val);
}
if (isLastCell && possibilities.Count > 0)
{
numericGrid[row][col] = (int)possibilities[0];
return true;
}
foreach (int val in possibilities)
{
numericGrid[row][col] = val;
if (Compute(nNextRow, nNextCol, applyPerfectSquares))
return true;
}
numericGrid[row][col] = (int)DukuValues.EMPTY;
return false;
}
Points of Interest
This turned out to be a decent example of dynamic user interface creation using C# and Windows Forms. The doku algorithm I created relies heavily on recursion in C#, and passes grids of data by reference in order to keep memory usage low.
History
This is the initial version of this code. I hope to add optimization in future to quickly detect the unsolvable grids. I may multi-thread it, so the UI can be updated with the status during longer computations.
License
This article has no explicit license attached to it, but may contain usage terms in the article text or the download files themselves. If in doubt, please contact the author via the discussion board below. A list of licenses authors might use can be found here.