Sudoku Solver and Generator

Jörgen Pramberg

Rate me:

4.55/5 (42 votes)

3 Aug 2010CPOL5 min read

434.7K

26.3K

162

Solves and generates Sudokus

Introduction

A while back, a colleague of mine introduced me to a game called Sudoku. I was totally ignorant of this game, but soon got the rules explained and then realized pretty quickly that it would be a lot faster to make a program for this than solve even one single puzzle!

Sudoku Rules

The rules for Sudoku are simple. You have a board with 9x9 cells, the board is further divided into nine sub squares with 3x3 cells each. In every sub square, in vertical and horizontal lines, you have to put the numbers 1-9 once and only once.

When creating a Sudoku, we must keep in mind that there can be only one solution for it, otherwise it is not considered a real Sudoku.

Solve the Puzzle

When the class is initialized and a Sudoku puzzle has been set to solve, we can let the function Solve() start its business. In each iteration, we want to locate the spot on the board with the maximum information. We start with an initial set M with all possible solutions for the spot:

// Set M of possible solutions
byte[] M = {0,1,2,3,4,5,6,7,8,9};

We then remove all the used occurrences in the vertical direction:

for(int a = 0; a < 9; a++)
    M[m_sudoku[a,x]] = 0;

and the horizontal direction:

for(int b = 0; b < 9; b++)
    M[m_sudoku[y,b]] = 0;

Last, we remove all the used occurrences in the sub square. To speed up the feasibility test and simplify the code, I decided to use look-up tables for the sub squares. First, we get an index into the sub square table from our current position by using a table that maps locations to sub squares:

int squareIndex = m_subSquare[y,x];

Then we get the actual position into the two-dimensional array by using a sub index array:

EntryPoint p = m_subIndex[squareIndex,c];

This last code snippet is used inside a loop that removes all occurrences in the square:

for(int c = 0; c < 9; c++)
{
    EntryPoint p = m_subIndex[squareIndex,c];
    M[m_sudoku[p.x,p.y]] = 0;
}

We then calculate the cardinality of the set M:

int cM = 0;
for(int d = 1; d < 10; d++)
    cM += M[d] == 0 ? 0 : 1;

If the cardinality of the current set is less than the smallest before that, the current spot is the best evaluated so far:

if(cM < cMp)
{
    cMp = cM;
    Mp = M;
    xp = x;
    yp = y;
}

The smallest cardinality cMp was initially set to 10 and if that hasn't been changed, we can be certain that there are no empty spots on the board and we can exit successfully:

if(cMp == 10)
    return true;

On the other hand, if the cardinality of the smallest set was 0, i.e., there was an empty set M of feasible elements, we can be sure that there isn't a solution and we have to back track:

if(cMp == 0)
    return false;

When all the base cases have been accounted for, we can start the iterative process that tries every element of M in turn:

for(int i = 1; i < 10; i++)
{
    if(Mp[i] != 0)
    {
        m_sudoku[yp,xp] = Mp[i];
        if(Solve())
            return true;
    }
}

// Restore to original state.
m_sudoku[yp,xp] = 0;
return false;

The loop replaces the unused spot with each element of M in turn and tries to solve in a recursive manner. When M gets exhausted, we return false indicating there is no solution. If the function returned successfully, a solution can be read in the Data property as in the example:

...
Sudoku s = new Sudoku();
s.Data = SudokuToSolveFor;
if(s.Solve())
    byte[,] SudokuSolved = s.Data;
else
    // No solution
...

Generate a Sudoku

I soon realized that it was too boring entering Sudokus by hand and set for the task to generate them. My requirements were that you should be able to indicate how many spots should be filled in and give a possible start pattern. If the possible start pattern didn't work out on the first try it could be thrown away and an entire new pattern could be generated, otherwise we might be stuck with a pattern that doesn't have a solution, and considering the size of the entire Sudoku space that is quite bad complexity wise the program does a set number of retries.

The function Generate(int nodes, int numberOfTries = 1000000) is where all the functionality is located. We start by calculating how many spots are used in the current data set ~~and then decide whether we'll start up fresh or~~ and then generate an entire new Sudoku:

int num = GetNumberSpots();

if(!IsSudokuFeasible() || num > nodes)
{
    // The supplied data is not feasible, clear data.
    // - or -
    // The supplied data has too many nodes set, clear data.
    return Tuple.Create(0L, false);
}

The set number of spots are generated and then the Sudoku is tested for uniqueness:

do
{
    var originalData = Data;

    long tries = 0;
    for (; tries < numberOfTries; tries++)
    {
        // Try to generate spots
        if (Gen(spots - num))
        {
            // Test if unique solution.
            if (IsSudokuUnique())
            {
                return Tuple.Create(tries, true);
            }
        }

        // Start over.
        Data = originalData;
    }

    return Tuple.Create(tries, false);

This loop goes on ~~forever until a solution has been found~~ for the set number of iterations. There is room for improvement here if we want to be able to abort in mid search. The Gen(int spots) function starts by generating a random spot on the 9x9 board. To get determinism in the unit tests, the random generator implements the IRandomizer interface and is nondeterministic in production but deterministic for unit tests.

do
{
    xRand = Randomizer.GetInt(9);
    yRand = Randomizer.GetInt(9);
} while(m_sudoku[yRand,xRand] != 0);

For each randomized spot, we have to check for the feasible values, pretty much done in the same style as in the solver:

// Set M of possible solutions
byte[] M = {0,1,2,3,4,5,6,7,8,9};

// Remove used numbers in the vertical direction
for(int a = 0; a < 9; a++)
    M[m_sudoku[a,xRand]] = 0;

// Remove used numbers in the horizontal direction
for(int b = 0; b < 9; b++)
    M[m_sudoku[yRand,b]] = 0;

// Remove used numbers in the sub square.
int    squareIndex = m_subSquare[yRand,xRand];
for(int c = 0; c < 9; c++)
{
    point p = m_subIndex[squareIndex,c];
    M[m_sudoku[p.x,p.y]] = 0;
}

int cM = 0;
// Calculate cardinality of M
for(int d = 1; d < 10; d++)
    cM += M[d] == 0 ? 0 : 1;

If the cardinality is larger than zero, we get a random sample from the feasible set M:

if(cM > 0)
{
    int e = 0;

    do
    {
        // Randomize number from the feasible set M
        e =  Randomizer.GetInt(1,10);
    } while(M[e] == 0);

    // Set number in Sudoku
    m_sudoku[yRand,xRand] = (byte)e;
}

If the set M is empty, this can't be a Sudoku and we restart the process until we find a non-empty set M. When all the given spots have been generated, we try for uniqueness in the function TestUniquness(). The test for uniqueness is done by trying to generate more than one solution; as soon as more than one exists, the generated set will not be feasible and a new one is generated:

... // same as in Solve()

int success = 0;
for(int i = 1; i < 10; i++)
{
    if(Mp[i] != 0)
    {
        m_sudoku[yp,xp] = Mp[i];

        switch(TestUniqueness())
        {
            case Ret.Unique:
                success++;
                break;

            case Ret.NotUnique:
                return Ret.NotUnique;

            case Ret.NoSolution:
                break;
        }

        // More than one solution found?
        if(success > 1)
            return Ret.NotUnique;
    }
}

...

switch(success)
{
    case 0:
        return Ret.NoSolution;

    case 1:
        return Ret.Unique;

    default:
        // Won't happen.
        return Ret.NotUnique;
}

Sample Application

To demonstrate how to use the class, I have made a small, rudimentary application using Windows Forms. From this, you can generate, solve, print, load and save Sudokus.