Click here to Skip to main content
13,139,254 members (54,285 online)
Click here to Skip to main content
Add your own
alternative version


44 bookmarked
Posted 4 Jan 2006

Sudoku (Suduku) Solver

, 17 Jan 2006
Rate this:
Please Sign up or sign in to vote.
Source code for a Sudoku solver.


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.


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.


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.


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


About the Author

Craig Spitzkoff
Web Developer
United States 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, 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...

Comments and Discussions

GeneralRe: You've missed the point Pin
Gabriel 211-Jan-06 10:04
memberGabriel 211-Jan-06 10:04 
GeneralRe: Brute force--not elegent Pin
The_Mega_ZZTer10-Jan-06 19:34
memberThe_Mega_ZZTer10-Jan-06 19:34 
GeneralRe: Brute force--not elegent Pin
Will Gray11-Jan-06 10:19
memberWill Gray11-Jan-06 10:19 
GeneralRe: Brute force--not elegent Pin
Arbitrary Programmer11-Jan-06 11:15
memberArbitrary Programmer11-Jan-06 11:15 
GeneralRe: Brute force--not elegent Pin
Josh Smith12-Jan-06 12:19
memberJosh Smith12-Jan-06 12:19 
GeneralRe: Brute force--not elegent Pin
Dwayne Wilkinson6-Feb-06 11:35
memberDwayne Wilkinson6-Feb-06 11:35 
GeneralRe: Brute force--not elegent Pin
Ed Korsberg26-Feb-06 9:28
memberEd Korsberg26-Feb-06 9:28 
GeneralRe: Brute force--not elegent Pin
Will Gray27-Feb-06 3:51
memberWill Gray27-Feb-06 3:51 
GeneralVery nice. Pin
UsualDosage4-Jan-06 8:24
memberUsualDosage4-Jan-06 8:24 
GeneralRe: Very nice. Pin
Herbert Sauro10-Jan-06 6:59
memberHerbert Sauro10-Jan-06 6:59 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.170915.1 | Last Updated 18 Jan 2006
Article Copyright 2006 by Craig Spitzkoff
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid