Wednesday, February 4, 2009

Sudoku Genetic Algorithm: Introduction

What Is Sudoku?
Sudoku is a recently introduced, Japanese number puzzle where the objective is to fill a 9x9 grid so that each row, column, and 3x3 sub grid, contains numbers 1 through 9. The grids are usually partially filled and so it's the job of the solver to complete the remaining empty cells, without violating these. Sudoku problems range from easy to hard, where easy grids have more than one possible solution, and hard, where the grids have only one unique solution.

Sudoku puzzle with solution numbers marked in red. Source: Wikipedia

Why Use A Genetic Algorithm?

...because curiosity killed the cat, that's why!

Genetic Algorithms to which I'll now abbreviate to GA, is an interesting means to solving a problem. Though in this domain, they certainly don't provide a performance increase, they're often used in engineering to solve problems to which the solution space is so vast, there exists no algorithmic approach and Monte Carlo methods simply skim the surface of all possible solutions.

Gross Over-Simplification:
We maintain a population of ideally diverse solutions, to which each individuals fitness (effectiveness of solving a given problem) is evaluated. The highest ranking individuals are chosen to seed the next generation, with low ranking individuals discarded. This process repeats until some given threshold has been breached. This process effectively refines good solutions in an attempt to increase their fitness, so much so that they solve the problem. Note that this is a Gross Over-Simplification and much work goes into the degree of seeding, mutating solutions and even the evaluation function... GAs are not a one-stop-shop to solve world hunger.

In general, we use a GA to solve Sudoku puzzles because we can and it provides a more holistic approach to solving a problem.

In this series of posts, we'll explore the various aspects of implementing a Sudoku GA including the pitfalls and misconceptions of GAs in general.