Using Genetic Algorithms to come up with Sudoku Puzzles

Figure 1 - Best Sudoku Genome from Generation 900

Well there is a new craze here in New York City... Sudoku.  You see it in the bookstores, the subways, and on the newstands.   The closest analogy  I can come up with to describe Sudoku is the Rubicks Cube , but easier.  The way Sudoku works is you are given a grid like the one shown in figure 2 containing numbers.   The object of Sudoku is to fill the grid with all the numbers in such a way that each row, column, and 3x3 bold square has a unique numbers 1-9.   There exists only one solution to the puzzle, so when you finish the puzzle you can check it against an answer key.  If you are interested in Sudoku, you can go to the website http://www.sudoku.com/ and check it out.

Figure 2 - Sample Sudoku puzzle

Having gotten a little hooked on these brain-spinning puzzles myself,  I decided to write a genetic algorithm to create possible Sudoku solutions.  It took a while, but I finally came up with a fitness function, mutation, and crossover function that would help produce a solution as shown in figure 3.  Note that it took many, many generations to arrive at a unique solution for the gene population, but eventually it does happen. (A fitness of -->1 indicates that we finally found a Sudoku Square).

Figure 3 - Sudoku Solution after 36,700 generations of genes

Design

The Design was taken from the Genetic Algorithm Mastermind article and adapted to produce a Sudoku Genomes.  The SudokuGenome contains a 9x9 rectangular integer array.  The Genome can do basic GA functions such as Mutate, Crossover, Calculate Fitness, and Initialize.  The Population class contains the gene pool and can manipulate the genes in the pool to produce the next generation.  If you want to understand more about Genetic Algorithms, please read my article on the subject on C# Corner, Implementing a Genetic Algorithms in C# and .NET. 

Figure 4 - UML Design Reverse Engineered using WithClass

Fitness Function

As always, coming up with the proper fitness function for the genetic algorithm is the greatest challenge.  The way we determined the fitness function was using three hashtables that act as histograms.  The fitness algorithm first goes through each column of the Sudoku Genome and uses the number contained in the cell as a hash key.  A value is added to the ColumnMap with the hash key in each cell.  After an  entire column is traversed, the algorithm looks at the count of the ColumnMap .  If every key in the column is unique, then the ColumnMap contains a total of 9 values.  If the column contains a few duplicates, the total count in the ColumnMap will always be less than 9.  The count can then be used as a representative fitness of uniqueness for a particular column.  By adding this number for all columns, we can come up with a fitness for uniqueness of columns.  We can then perform the same exact technique for determining row uniqueness.  The RowMap is populated with keys from each cell in a row of the Sudoku grid.  If the row is entirely unique, then the RowMap will contain 9 entries.   The same technique is also used for each 3x3 cell grouping (shown in figure 1).  The SquareMap is populated with cell values as keys for this hashtable.  Listing 1 demonstrates the entire fitness function operating  on our Sudoku Gene's Multidimensional Array.

Listing 1 - Fitness function for the Sudoku Grid

/// <summary>
/// The Calculate Sudoku Fitness uses the uniqueness of columns, rows
/// and 3x3 squares in the grid to determine a fitness value
/// </summary>
/// <returns></returns>
private float CalculateSudokuFitness()
{
// set fitnesses for columns, rows, and squares initially to 0
float fitnessColumns = 0;
float fitnessRows = 0;
float fitnessSquares = 0;
// go through each column
for (int i = 0; i < 9; i++)
{
// Go through each cell in a column, add it to the ColumnMap according
// to the cell value
ColumnMap.Clear(); // clear the column map for each new column
for (int j = 0; j < 9; j++)
{
// check for uniqueness in row
if (ColumnMap[TheArray[i,j]] == null)
{
ColumnMap[TheArray[i,j]] = 0;
}
ColumnMap[TheArray[i,j]] = ((int)ColumnMap[TheArray[i,j]]) + 1;
}
// accumulate the column fitness based on the number of entries in the ColumnMap
fitnessColumns += (float)(1.0f/ (10-ColumnMap.Count))/9.0f;
//fitnessColumns += (float)Math.Exp(ColumnMap.Count*10 - 90)/9;
}
// go through each row next
for (int i = 0; i < 9; i++)
{
// Go through each cell in a row, add it to the RowMap according
// to the cell value
RowMap.Clear(); // clear the row map for each new row
for (int j = 0; j < 9; j++)
{
// check for uniqueness in row
if (RowMap[TheArray[j,i]] == null)
{
RowMap[TheArray[j,i]] = 0;
}
RowMap[TheArray[j,i]] = ((int)RowMap[TheArray[j,i]]) + 1;
}
// accumulate the row fitness based on the number of entries in the RowMap
fitnessRows += (float)(1.0f/ (10-RowMap.Count))/9.0f;
// fitnessRows += (float)Math.Exp(RowMap.Count*10 - 90)/9;
}
// go through next square
for (int l = 0; l < 3; l++)
{
for (int k = 0; k < 3; k++)
{
// Go through each cell in a 3 x 3 square, add it to the SquareMap according
// to the cell value
SquareMap.Clear(); // Clear the square map for each 3 x 3 square
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
// check for uniqueness in row
// check for uniqueness in row
if (SquareMap[TheArray[i + k*3,j + l*3]] == null)
{
SquareMap[TheArray[i+k*3,j+l*3]] = 0;
}
// accumulate the square fitness based on the number of entries in the SquareMap
SquareMap[TheArray[i + k*3,j + l*3]] = ((int)SquareMap[TheArray[i + k*3,j + l*3]]) + 1;
}
}
fitnessSquares += (float)(1.0f/ (10-SquareMap.Count))/9.0f;
}
}// The fitness of the entire Sudoku Grid is the product
// of the column fitness, row fitness and 3x3 square fitness
CurrentFitness = fitnessColumns * fitnessRows * fitnessSquares;
return CurrentFitness;
}
Conclusion

Sudoku is the latest fad for puzzle addicts and I suspect it's here to stay.  This article demonstrates how to generate a fully populated Sudoku puzzle using a genetic algorithm.  In our next article we will tackle solving actual Sudoku Puzzles with GA's like the one shown in figure 2.  In the meantime, you can wipe that puzzled  expression off your face, and delve into Sudoku in the land of C# and .NET.

Affiliates

Sudoku for Kids - 120 Printable Puzzles

Sudoku Secrets