15,943,233 members
Articles / Programming Languages / C#

# Sudoku (Suduku) Solver

Rate me:
17 Jan 20063 min read 127.2K   3.3K   46   20
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.

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

Written By
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.

 First Prev Next
 Love Suduku Vandretta15-Jun-07 20:19 Vandretta 15-Jun-07 20:19
 Beautiful Sudoku AghaKhan18-Jan-07 10:36 AghaKhan 18-Jan-07 10:36
 awesome dwight017-Jan-06 20:35 dwight0 17-Jan-06 20:35
 optimize Resetchoice Gilbert Chauvaux14-Jan-06 8:12 Gilbert Chauvaux 14-Jan-06 8:12
 Re: optimize Resetchoice Craig Spitzkoff14-Jan-06 9:31 Craig Spitzkoff 14-Jan-06 9:31
 Brute force--not elegent Will Gray10-Jan-06 10:10 Will Gray 10-Jan-06 10:10
 Re: Brute force--not elegent Craig Spitzkoff10-Jan-06 11:16 Craig Spitzkoff 10-Jan-06 11:16
 Re: You've missed the point Will Gray10-Jan-06 11:42 Will Gray 10-Jan-06 11:42
 Re: You've missed the point o_pontios10-Jan-06 12:56 o_pontios 10-Jan-06 12:56
 Re: You've missed the point Arbitrary Programmer10-Jan-06 14:09 Arbitrary Programmer 10-Jan-06 14:09
 Re: You've missed the point Gabriel 211-Jan-06 10:04 Gabriel 2 11-Jan-06 10:04
 Re: Brute force--not elegent The_Mega_ZZTer10-Jan-06 19:34 The_Mega_ZZTer 10-Jan-06 19:34
 Re: Brute force--not elegent Will Gray11-Jan-06 10:19 Will Gray 11-Jan-06 10:19
 Re: Brute force--not elegent Arbitrary Programmer11-Jan-06 11:15 Arbitrary Programmer 11-Jan-06 11:15
 Re: Brute force--not elegent Josh Smith12-Jan-06 12:19 Josh Smith 12-Jan-06 12:19
 Re: Brute force--not elegent Dwayne Wilkinson6-Feb-06 11:35 Dwayne Wilkinson 6-Feb-06 11:35
 Re: Brute force--not elegent Ed Korsberg26-Feb-06 9:28 Ed Korsberg 26-Feb-06 9:28
 Re: Brute force--not elegent Will Gray27-Feb-06 3:51 Will Gray 27-Feb-06 3:51
 Very nice. DreamInHex4-Jan-06 8:24 DreamInHex 4-Jan-06 8:24
 Re: Very nice. Herbert Sauro10-Jan-06 6:59 Herbert Sauro 10-Jan-06 6:59
 Last Visit: 31-Dec-99 18:00     Last Update: 21-Jul-24 5:29 Refresh 1