Click here to Skip to main content
Click here to Skip to main content

Sudoku (Suduku) Solver

, 17 Jan 2006
Rate this:
Please Sign up or sign in to vote.
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)
            possibilities.Add(val);

    }

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

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

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

Comments and Discussions

 
GeneralBeautiful Sudoku PinmemberBilloKhan18-Jan-07 10:36 

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

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

| Advertise | Privacy | Mobile
Web02 | 2.8.140721.1 | Last Updated 18 Jan 2006
Article Copyright 2006 by Craig Spitzkoff
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid