This is perhaps not so surprising considering how evolution creates vastly different species (solutions) for different environmental conditions (problems).

Here is the pseudo-code of Evolutionary Algorithm:

Here is a diagrammatic representation:

It is simple really. You have a pool of population which is made of many solutions. At each iteration select fit parents, recombine their genes and allow mutation to make 2 distinct children. Sort the population by fitness score. Let the worst 2 die, and continue iteration until the best fit is found.

In the Eight Queens problem, from the chess-board, the array size is 8x8 = 64, whereas in Sudoku it is 9x9 = 81.

The fitness function calculates a positive number which increases with the level of fitness.

Usually the worst fit solution is calculable. In the case of Sudoku this is one of the worst solutions:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

This is not even a legal acceptable

**final**solution is Sudoku. But any solution in evolutionary landscape is legally born. When an individual solution's fitness is calculated it may or may not survive the next run (generation).

A perfectly fit Sudoku solution is achieved when all 1-9 digits present in 3x3 matrices along with no-clashing digits present across rows or columns.

Therefore in Sudoku the unfitness score is a number calculated by counting number of times a given digit is repeated across a row or a column and also adding the missing set of digits in all 3x3 sub-matrices.

The resultant fitness score is normalised form of unfitness score, i.e. fitness score is calculated by subtracting the calculated unfitness score from the maximum unfitness score (378).

Two runs from a typical output are given below:

-----------------------------------------

Run: 1

Best score 378

Found best '1' in 3540 iterations.

[4, 1, 3, 9, 8, 6, 2, 5, 7]

[7, 2, 9, 5, 3, 4, 8, 1, 6]

[6, 5, 8, 2, 1, 7, 3, 9, 4]

[2, 3, 7, 4, 5, 8, 9, 6, 1]

[8, 6, 4, 1, 2, 9, 5, 7, 3]

[1, 9, 5, 6, 7, 3, 4, 2, 8]

[9, 4, 2, 8, 6, 1, 7, 3, 5]

[3, 8, 6, 7, 9, 5, 1, 4, 2]

[5, 7, 1, 3, 4, 2, 6, 8, 9]

-----------------------------------------

Run: 2

Best score 378

Found best '1' in 8636 iterations.

[2, 7, 5, 3, 9, 4, 8, 6, 1]

[8, 1, 3, 5, 2, 6, 7, 9, 4]

[9, 6, 4, 8, 1, 7, 2, 5, 3]

[4, 2, 6, 9, 8, 3, 1, 7, 5]

[1, 8, 7, 2, 4, 5, 9, 3, 6]

[3, 5, 9, 6, 7, 1, 4, 2, 8]

[5, 4, 1, 7, 3, 2, 6, 8, 9]

[6, 9, 2, 1, 5, 8, 3, 4, 7]

[7, 3, 8, 4, 6, 9, 5, 1, 2]

...

I still have to tune the program for better performance. I may try different mutation or recombination strategies, play with population sizes and selection strategies to shorten the time required to create a sudoku solution.

The prototype was written in Python. Eventually I would like to port the algorithm to IOS 7 for creating the sexiest sudoku app ever.

The Evolutionary Algorithm I used was from the book Introduction to Evolutionary Computing

^{1}.

References:

1. Introduction to Evolutionary Computing, Agoston E. Eiben, J.E. Smith, Springer, 01/01/2003

2. Sudoku - Wikipedia

3. Eight Queens - Wikipedia