Sudoku Solving GA
Target: develop a Genetic Algorithm that will solve Sudoku puzzles.
By: Aviv Ron (ronav@cs.bgu.ac.il)
(www.cs.bgu.ac.il/~ronav)
Genome: A row-ordered list of the empty cells in the grid,
with each cell having possible values in the puzzles legal range.
Fitness value: For each cell count the number of penalties, where
a penalty point is given if there is an identical value in the same row,
column, or box. Thus, each cell can accumulate up to 3 penalty points, and the
worst score is 48 for the 2x2 puzzles (3 X 16) and 108 (3 X 36) for the 6x6 puzzles.
The objective is to minimize fitness to zero.
Selection: Tournament Selection (The tournament size will be
discussed later).
Crossover: a simple two point crossover. Genomes always stay
legal this way.
Mutation: choose two bits in the genome and swap them.
Application was built in C#
because I wanted a nice GUI to interact with.
Note: the population size, crossover rate etc… for each
experiment can be seen in the screen shot, so I didn’t write them down.
First trial: a simple 4x4 sudoku puzzle:
Luckily a solution was found
on generation 9… lets try again:
This time the GA got stuck on
a local minimum of 11 and could not progress.
I try to lower the tournament
size in order to encourage versatility:
Tournament size reducing
didn’t help a lot. We can see more versatility in the average fitness but it
wasn’t enough to get the GA from its local minimum of 8.
Let’s introduce a new factor
now: old punishment. I will kill individuals that haven’t evolved for x
generations and replace them with new ones.
First try with old Punishment
of 4 generations:
A solution was found after 11
generations. Only one individual was replace by the
old punishment. Lets try again with a different 4x4
puzzle (no.3):
The results:
A solution was found after 148
generations. The GA managed to get out of the local minimum with the help of
the old punishment.
38 old individuals were
replaced by the old punishment.
The solution found:
Now let’s move to bigger and
harder puzzles. Start with the first 6x6 puzzle from the assignment:
The GA didn’t manage to find
the solution and got stuck on a local minimum of 6:
The old penalty replaced 106
individuals, but it wasn’t enough to overcome the local minimum.
Lets try to raise the mutation rate and lower the age of
individuals replaced by the old penalty:
This time the GA did a little
better and managed to get out of an 8 point local minimum to a 4 point Fitness
at generation 338.
942 individuals were replaced
by the old penalty.
Now I try to introduce the Earth
Quake: the earth quake mode will check the population every generation and
if the generation don’t improve (the best and avg fitness are very close to each other) it will replace a
percentage of the population with new individuals.
This approach didn’t come up
with results. The GA didn’t manage to improve thanks to the EQ:
Ill try it again with the EQ
set to work after 80 generations and replace 75% of the population:
The EQ seems as a bad idea…ill
try again this puzzle without EQ and with a high mutation rate and old
punishment:
The GA did good and almost
found the proper solution a high mutation rate seems to help getting out of the
local minimum.
The first run:
Second run:
Conclusions: solving sudoku puzzles
with GA isn’t such a good idea… the GA most of the times comes up with almost
best solution , but in the case of the sudoku
puzzle an almost solution doesn’t count. The aspects which helped the GA were a
high mutation rate and the old penalty, but they weren’t enough to take the
algorithm to reaching the correct solution.
The Code for this app can be
found here,
and an installer package here.
To install the application unzip the file you download, double click the setup.exe.
The application will be installed on your computer and a shortcut will be
created on your desktop called “
The application can be
installed only on a windows OS.