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