Saturday, April 22, 2006

Evolutionary sudoku solving

Alberto, me, and Simon recently got our paper on evolutionary sudoku solving accepted at CEC 2006. We thought we were the first researchers in the world to apply evolutionary algorithms to Sudoku, but according to one of the reviewers, we actually came second, as another paper on EC and Sudoku was accepted to Euro-GP a month or so earlier.

Anyway, our experiments worked really well. A quick introduction, for those who don't think in terms of evolutionary algorithms: We start with the empty sudoku grid, empty except for the fixed positions that define the puzzle. The algorithm, in its very simplest version, then fills in the empty positions with random numbers between one and nine. At each generation, a random change (mutation) was made to each grid, by changing one of the non-fixed numbers to another random number between one and nine. At the end of each generation, the fitness of each grid was evaluated by counting the number of unique elements in each row, grid and square. The grids with highest fitness were kept for next generation, and those with lower fitness were replaced with mutated clones of those with higher fitness, just like in nature. After a number of generations, such an algorithm actually solves most, if not all, Sudoku problems!

Not that our evolutionary algorithms solved sudoku grids faster than existing methods that take into account the structure of the problem - it is doubtful whether evolution will ever do that, at least for standard-size grids. But our main aim was to verify some predictions from Alberto's theory using Sudoku as a testbed.

Alberto's theory is about geometric crossover. In my description I omitted crossover - when a new individuals (in this case a new Sudoku grid) is created by mixing two parents (in this case two other Sudoku grids). Actually, many evolutionary algorithms don't use crossover, because it is so tricky to get it right - it can easily end up doing more harm than good. But when it's used right it can actually improve the efficiency of an evolutionary algorithm dramatically. The highly mathematical theory of Alberto is about exactly what sort of crossover is appropriate for what problem representation. Greatly simplified, it says that the offspring should be somewhere between its parents in the multidimensional space of representations. And it turned out that the crossover operators designed according to this theory indeed were very effective.

But enough about this - go read the paper to get to know more! The source code is available if you want to do your own experiments.

1 comment:

Bruce Fredman said...

Hi,
We at Chessboss.com strongly believe in necessity of chess to increase both knowledge and understanding. It is unfortunate that the oldest game in the world (Chess) has a very little fan base, ChessBoss.com aims to change that. We understand the importance of blogs and the information made available on them. We are working towards building a strong fan base around our FREE chess server to better increase the use of Chess online. Your blog seems to have a large viewing public and seems to hold great information which I would love to make available to my viewing public.

I have included the code for the ChessBoss.com banner within the body of this email along with textual link information. I would be pleased to offer you the ChessBoss.com featured blogger badge to post on your site, recognizeing your blog as a leading contributor to the Chess community. Thank you for your great work and dedication, we look forward to your response!Please reply me back with subject line of your Url to avoid spam and to make sure YOU get the Award.

Thank you.