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