12,949,083 members (63,176 online)
alternative version

#### Stats

106K views
44 bookmarked
Posted 4 Jan 2006

# Sudoku (Suduku) Solver

, 17 Jan 2006
 Rate this:
Source code for a Sudoku solver.

## 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.

```/// <summary>
/// Continues the computation of the answer
/// to the Duku grid at a specific cell. This
/// function is used recursively to compute the entire grid.
/// </summary>
/// <param name="applyPerfectSquares">If true, this will apply
/// the rule of the perfect squares to the Grid.
/// This should only be used on a grid of perfect square dimensions
/// (1, 4, 9, 16, etc.). This will enforce an additional rule of
/// having each sub square grid contain the numbers 1-n.
/// In all other cases only rows and columns are checked</param>
/// <returns></returns>
public bool Compute(int row, int col, bool applyPerfectSquares)
{
// determine the next row/col
int nNextRow = row;
int nNextCol = col;
bool isLastCell = !NextRowCol(ref nNextRow, ref nNextCol);

// if we are on a locked cell, move to the next cell
if (statusGrid[row][col] == DukuStatus.LOCKED)
{
// deterministic step. If we've reached the end of
// our grid and it is locked, we have success
if (isLastCell)
return true;

return Compute(nNextRow, nNextCol, applyPerfectSquares);
}

// determine the possibilities for this cell
ArrayList possibilities = new ArrayList(nRowsColumns);

// loop for each numeric value it could be
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;
}
}

// this will apply the rule of perfect squares
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 the value was not already used, add it to the list
if (!bFound)

}

// deterministic step. If we've reached the end of our
// grid and we have an option, set it and we are done
if (isLastCell && possibilities.Count > 0)
{
numericGrid[row][col] = (int)possibilities[0];
return true;
}

// now we have our list of possible values.
// Loop through, setting the value
// and calling Compute on the next cell
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.

A list of licenses authors might use can be found here

## Share

 Web Developer United States
Craig currently works as the VP of Development at Raizlabs Corporation, a User Interface and Design consulting firm based in Brookline, MA. Previous to this Craig spent time at various companies in the defense industry such as Lockheed Martin, BAE Systems and Tybrin, where he worked on PC based Mission Planning software.

As a side project, Craig founded JobVent.com, a site where people can post reviews about their jobs and employers.

Craig graduated from Tufts University in 2000 with a B.S. in Computer Science and a minor in Multimedia Arts. Craig completed his M.B.A at Northeastern University in 2003.

## You may also be interested in...

 View All Threads First Prev Next
 Beautiful Sudoku BilloKhan18-Jan-07 10:36 BilloKhan 18-Jan-07 10:36
 Last Visit: 31-Dec-99 18:00     Last Update: 25-May-17 1:40 Refresh 1