Sudoku (Suduku) Solver

• Download demo project - 225 Kb
• Download source - 15.5 Kb

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.