IntroductionSudoku Rules
Solve the Puzzle
Collapse | Copy Code// Set M of possible solutions
byte[] M = {0,1,2,3,4,5,6,7,8,9};
Collapse | Copy Codefor(int a = 0; a < 9; a++)
M[m_sudoku[a,x]] = 0;
Collapse | Copy Codefor(int b = 0; b < 9; b++)
M[m_sudoku[y,b]] = 0;
Collapse | Copy Codeint squareIndex = m_subSquare[y,x];
Collapse | Copy CodeEntryPoint p = m_subIndex[squareIndex,c];
Collapse | Copy Codefor(int c = 0; c < 9; c++)
{
EntryPoint p = m_subIndex[squareIndex,c];
M[m_sudoku[p.x,p.y]] = 0;
}
Collapse | Copy Codeint cM = 0;
for(int d = 1; d < 10; d++)
cM += M[d] == 0 ? 0 : 1;
Collapse | Copy Codeif(cM < cMp)
{
cMp = cM;
Mp = M;
xp = x;
yp = y;
}
Collapse | Copy Codeif(cMp == 10)
return true;
Collapse | Copy Codeif(cMp == 0)
return false;
Collapse | Copy Codefor(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;
Collapse | Copy Code...
Sudoku s = new Sudoku();
s.Data = SudokuToSolveFor;
if(s.Solve())
byte[,] SudokuSolved = s.Data;
else
// No solution
...
Generate a Sudoku
Collapse | Copy Codeint 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);
}
Collapse | Copy Codedo
{
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);
Collapse | Copy Codedo
{
xRand = Randomizer.GetInt(9);
yRand = Randomizer.GetInt(9);
} while(m_sudoku[yRand,xRand] != 0);
Collapse | Copy Code// 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;
Collapse | Copy Codeif(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;
}
Collapse | Copy Code... // 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
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
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!
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.
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:
We then remove all the used occurrences in the vertical direction:
and the horizontal direction:
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:
Then we get the actual position into the two-dimensional array by using a sub index array:
This last code snippet is used inside a loop that removes all occurrences in the square:
We then calculate the cardinality of the set
M:
If the cardinality of the current set is less than the smallest before that, the current spot is the best evaluated so far:
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:
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:
When all the base cases have been accounted for, we can start the iterative process that tries every element of
M in turn:
The loop replaces the unused spot with each element of
M in turn and tries to solve in a recursive manner. When Mgets 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:
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 and then decide whether we'll start up fresh or and then generate an entire new Sudoku:
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
The set number of spots are generated and then the Sudoku is tested for uniqueness:
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 theIRandomizer interface and is nondeterministic in production but deterministic for unit tests.
For each randomized spot, we have to check for the feasible values, pretty much done in the same style as in thesolver:
If the cardinality is larger than zero, we get a random sample from the feasible set
M:
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:
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.
Reference:
No comments:
Post a Comment