Click here to Skip to main content
11,504,689 members (70,694 online)
Click here to Skip to main content

Sudoku Solver and Generator

, 3 Aug 2010 CPOL 316.6K 19.1K 155
Rate this:
Please Sign up or sign in to vote.
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.

History

  • 31st July, 2010 - Article update
    • Submitted a bug fix that has been lying around for about five years
    • Migrated solution to Visual Studio 2010 and .NET 4.0
    • Split the solution in three assemblies
    • Added tuples and optional parameters (C# 4.0)
    • Added unit tests (Microsoft.VisualStudio.TestTools.UnitTesting)
  • 18th October, 2005 - Article submission
  • 2nd October, 2005 - Windows Forms framework
  • 25th September, 2005 - Sudoku class

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Jörgen Pramberg
Architect Visma
Sweden Sweden
No Biography provided

Comments and Discussions

 
QuestionGJFUJJFJK Pin
Rehab Musarreg10-Aug-13 23:58
memberRehab Musarreg10-Aug-13 23:58 
GeneralMy vote of 5 Pin
GregoryW14-May-13 20:22
memberGregoryW14-May-13 20:22 
QuestionMy Vote of 5 Pin
A_K_5-Jul-12 0:11
memberA_K_5-Jul-12 0:11 
GeneralSudoku variation Pin
Blubbo10-Aug-10 6:47
memberBlubbo10-Aug-10 6:47 
Generalhats off to you. Pin
Shivamkalra17-May-10 9:36
memberShivamkalra17-May-10 9:36 
GeneralMy vote of 1 Pin
kingofsathy7-Mar-10 3:04
memberkingofsathy7-Mar-10 3:04 
GeneralDissapointing Pin
disco9-Oct-09 11:31
memberdisco9-Oct-09 11:31 
Generalthe best sudoku solver Pin
karakaya1331-May-09 23:26
memberkarakaya1331-May-09 23:26 
GeneralVery good example Pin
thanhtungo3-Apr-07 16:49
memberthanhtungo3-Apr-07 16:49 
GeneralNot unique Pin
Subgurim7-Feb-07 14:32
memberSubgurim7-Feb-07 14:32 
GeneralRe: Not unique Pin
Subgurim8-Feb-07 0:55
memberSubgurim8-Feb-07 0:55 
GeneralRe: Not unique Pin
disco9-Oct-09 11:40
memberdisco9-Oct-09 11:40 
GeneralAlternative solver/generator Pin
ohadp29-Nov-05 22:11
memberohadp29-Nov-05 22:11 
GeneralBug in TestUniqueness Pin
Simon Egli6-Nov-05 23:23
memberSimon Egli6-Nov-05 23:23 
GeneralRe: Bug in TestUniqueness Pin
Jörgen Pramberg7-Nov-05 2:45
memberJörgen Pramberg7-Nov-05 2:45 
GeneralRe: Bug in TestUniqueness Pin
Hing7-Nov-05 4:08
memberHing7-Nov-05 4:08 
GeneralRe: Bug in TestUniqueness Pin
Jörgen Pramberg7-Nov-05 8:54
memberJörgen Pramberg7-Nov-05 8:54 
This bug was introduced when formatting the code for submission to code project.Blush | :O
The last listing should read:

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

// Restore to original state.
m_sudoku[yp,xp] = 0; ///** This must be here.

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

return success == 1;
GeneralRe: Bug in TestUniqueness Pin
Hing7-Nov-05 16:58
memberHing7-Nov-05 16:58 
GeneralRe: Bug in TestUniqueness Pin
Hing7-Nov-05 23:43
memberHing7-Nov-05 23:43 
GeneralRe: Bug in TestUniqueness Pin
Jörgen Pramberg8-Nov-05 0:48
memberJörgen Pramberg8-Nov-05 0:48 
GeneralRe: Bug in TestUniqueness Pin
Hing8-Nov-05 1:58
memberHing8-Nov-05 1:58 
GeneralRe: Bug in TestUniqueness Pin
Jörgen Pramberg8-Nov-05 2:14
memberJörgen Pramberg8-Nov-05 2:14 
GeneralRe: Bug in TestUniqueness Pin
Hing8-Nov-05 5:29
memberHing8-Nov-05 5:29 
GeneralRe: Bug in TestUniqueness Pin
Doncp8-Nov-05 6:50
memberDoncp8-Nov-05 6:50 
GeneralRe: Bug in TestUniqueness Pin
Hing8-Nov-05 14:34
memberHing8-Nov-05 14:34 
AnswerRe: Bug in TestUniqueness Pin
jeremyrst6-Dec-06 5:09
memberjeremyrst6-Dec-06 5:09 
GeneralRe: Bug in TestUniqueness Pin
egenas9-Mar-09 7:28
memberegenas9-Mar-09 7:28 
GeneralRe: Bug in TestUniqueness Pin
eluelu11-Sep-11 23:43
membereluelu11-Sep-11 23:43 
QuestionBugs or not? Pin
Hing3-Nov-05 17:44
memberHing3-Nov-05 17:44 
AnswerRe: Bugs or not? Pin
Hing3-Nov-05 23:26
memberHing3-Nov-05 23:26 
GeneralRe: Bugs or not? Pin
Hing6-Nov-05 1:12
memberHing6-Nov-05 1:12 
GeneralRe: Symmetric Pin
SrMerlini29-Nov-05 1:13
memberSrMerlini29-Nov-05 1:13 
GeneralRe: Symmetric Pin
Hing29-Nov-05 2:25
memberHing29-Nov-05 2:25 
GeneralRe: Symmetric Pin
SrMerlini29-Nov-05 3:18
memberSrMerlini29-Nov-05 3:18 
GeneralRe: Bugs or not? Pin
Jörgen Pramberg6-Nov-05 11:35
memberJörgen Pramberg6-Nov-05 11:35 
GeneralRe: Bugs or not? Pin
ogrig8-Nov-05 17:41
memberogrig8-Nov-05 17:41 
AnswerRe: Bugs or not? Pin
Jörgen Pramberg6-Nov-05 11:28
memberJörgen Pramberg6-Nov-05 11:28 
GeneralRe: Bugs or not? Pin
Hing6-Nov-05 15:07
memberHing6-Nov-05 15:07 
GeneralRe: Bugs or not? Pin
Jörgen Pramberg7-Nov-05 2:35
memberJörgen Pramberg7-Nov-05 2:35 
GeneralHarder Sudoku Pin
Anonymous25-Oct-05 15:54
sussAnonymous25-Oct-05 15:54 
GeneralRe: Harder Sudoku Pin
Jörgen Pramberg25-Oct-05 21:24
memberJörgen Pramberg25-Oct-05 21:24 
GeneralSuggestion Pin
Bernhard Hofmann18-Oct-05 4:47
memberBernhard Hofmann18-Oct-05 4:47 
GeneralRe: Suggestion Pin
Bernhard Hofmann18-Oct-05 7:26
memberBernhard Hofmann18-Oct-05 7:26 
GeneralRe: Suggestion Pin
Jörgen Pramberg18-Oct-05 10:12
memberJörgen Pramberg18-Oct-05 10:12 

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 | Terms of Use | Mobile
Web04 | 2.8.150520.1 | Last Updated 3 Aug 2010
Article Copyright 2005 by Jörgen Pramberg
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid