11,504,689 members (70,694 online)

# 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)

## About the Author

Architect Visma
Sweden
No Biography provided

## Comments and Discussions

 First Prev Next
 GJFUJJFJK Rehab Musarreg10-Aug-13 23:58 Rehab Musarreg 10-Aug-13 23:58
 My vote of 5 GregoryW14-May-13 20:22 GregoryW 14-May-13 20:22
 My Vote of 5 A_K_5-Jul-12 0:11 A_K_ 5-Jul-12 0:11
 Sudoku variation Blubbo10-Aug-10 6:47 Blubbo 10-Aug-10 6:47
 hats off to you. Shivamkalra17-May-10 9:36 Shivamkalra 17-May-10 9:36
 My vote of 1 kingofsathy7-Mar-10 3:04 kingofsathy 7-Mar-10 3:04
 Dissapointing disco9-Oct-09 11:31 disco 9-Oct-09 11:31
 the best sudoku solver karakaya1331-May-09 23:26 karakaya13 31-May-09 23:26
 Very good example thanhtungo3-Apr-07 16:49 thanhtungo 3-Apr-07 16:49
 Not unique Subgurim7-Feb-07 14:32 Subgurim 7-Feb-07 14:32
 Re: Not unique Subgurim8-Feb-07 0:55 Subgurim 8-Feb-07 0:55
 Re: Not unique disco9-Oct-09 11:40 disco 9-Oct-09 11:40
 Alternative solver/generator ohadp29-Nov-05 22:11 ohadp 29-Nov-05 22:11
 Bug in TestUniqueness Simon Egli6-Nov-05 23:23 Simon Egli 6-Nov-05 23:23
 Re: Bug in TestUniqueness Jörgen Pramberg7-Nov-05 2:45 Jörgen Pramberg 7-Nov-05 2:45
 Re: Bug in TestUniqueness Hing7-Nov-05 4:08 Hing 7-Nov-05 4:08
 Re: Bug in TestUniqueness Jörgen Pramberg7-Nov-05 8:54 Jörgen Pramberg 7-Nov-05 8:54
 This bug was introduced when formatting the code for submission to code project. 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;
 Re: Bug in TestUniqueness Hing7-Nov-05 16:58 Hing 7-Nov-05 16:58
 Re: Bug in TestUniqueness Hing7-Nov-05 23:43 Hing 7-Nov-05 23:43
 Re: Bug in TestUniqueness Jörgen Pramberg8-Nov-05 0:48 Jörgen Pramberg 8-Nov-05 0:48
 Re: Bug in TestUniqueness Hing8-Nov-05 1:58 Hing 8-Nov-05 1:58
 Re: Bug in TestUniqueness Jörgen Pramberg8-Nov-05 2:14 Jörgen Pramberg 8-Nov-05 2:14
 Re: Bug in TestUniqueness Hing8-Nov-05 5:29 Hing 8-Nov-05 5:29
 Re: Bug in TestUniqueness Doncp8-Nov-05 6:50 Doncp 8-Nov-05 6:50
 Re: Bug in TestUniqueness Hing8-Nov-05 14:34 Hing 8-Nov-05 14:34
 Re: Bug in TestUniqueness jeremyrst6-Dec-06 5:09 jeremyrst 6-Dec-06 5:09
 Re: Bug in TestUniqueness egenas9-Mar-09 7:28 egenas 9-Mar-09 7:28
 Re: Bug in TestUniqueness eluelu11-Sep-11 23:43 eluelu 11-Sep-11 23:43
 Bugs or not? Hing3-Nov-05 17:44 Hing 3-Nov-05 17:44
 Re: Bugs or not? Hing3-Nov-05 23:26 Hing 3-Nov-05 23:26
 Re: Bugs or not? Hing6-Nov-05 1:12 Hing 6-Nov-05 1:12
 Re: Symmetric SrMerlini29-Nov-05 1:13 SrMerlini 29-Nov-05 1:13
 Re: Symmetric Hing29-Nov-05 2:25 Hing 29-Nov-05 2:25
 Re: Symmetric SrMerlini29-Nov-05 3:18 SrMerlini 29-Nov-05 3:18
 Re: Bugs or not? Jörgen Pramberg6-Nov-05 11:35 Jörgen Pramberg 6-Nov-05 11:35
 Re: Bugs or not? ogrig8-Nov-05 17:41 ogrig 8-Nov-05 17:41
 Re: Bugs or not? Jörgen Pramberg6-Nov-05 11:28 Jörgen Pramberg 6-Nov-05 11:28
 Re: Bugs or not? Hing6-Nov-05 15:07 Hing 6-Nov-05 15:07
 Re: Bugs or not? Jörgen Pramberg7-Nov-05 2:35 Jörgen Pramberg 7-Nov-05 2:35
 Harder Sudoku Anonymous25-Oct-05 15:54 Anonymous 25-Oct-05 15:54
 Re: Harder Sudoku Jörgen Pramberg25-Oct-05 21:24 Jörgen Pramberg 25-Oct-05 21:24
 Suggestion Bernhard Hofmann18-Oct-05 4:47 Bernhard Hofmann 18-Oct-05 4:47
 Re: Suggestion Bernhard Hofmann18-Oct-05 7:26 Bernhard Hofmann 18-Oct-05 7:26
 Re: Suggestion Jörgen Pramberg18-Oct-05 10:12 Jörgen Pramberg 18-Oct-05 10:12
 Last Visit: 31-Dec-99 18:00     Last Update: 3-Jun-15 1:55 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    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