My Stuff

Artificial Intelligence: Solving Sudokus using Genetic Algorithms

Anthony Woudenberg, Jens van de Water, Leiden University April 28, 2009

1

Abstract

This paper is discussing our findings for the fourth and final exercise of Artifical Intellegence, in which we attempt to solve sudokus by using genetic algorithms. We present an analyses of both elitist– and steady state selection, and discuss the pros and cons of either approach.

2

Introduction

After the fad several years ago, only few readers still require introduction to the phenomenon “sudoku”. Still, for those few, a quick summary. A sudoku is a fairly popular number puzzle, where the challenge lies in reconstructing a nine by nine grid filled with numbers between one and nine. Contrary to popular belief, the sudoku did not originate in Japan. The puzzle as we came to know it was originally created by the American Howard Garms in 1979 under the name “Numbers in Place”. It got its popularity in the second half of the ’80s, when a Japanese company introduced it under the name Sudoku. It wasn’t until 2005 when the virus spread to the rest of the world. In essence, sudokus are Latin squares with an additional condition. The numbers one to nine are placed on a grid, so that every number appears exactly once in each row, column and block (see Figure 1). A typical sudoku has about 23 to 32 given numbers, the rest is left blank. The amount of givens does have influence on the difficulty of a puzzle, but isn’t the only factor involved. 1

There are several traditional techniques to solve a sudoku. In this paper however, we use a rather unique approach by using a genetic algorithm (GA). There doesn’t seem to be much material available about solving sudokus using this method. The only truly relevant work we found was by Matere and Koljonen [1]. This means that it’s not really known whether or not GA’s even perform well when solving sudokus. Since there are several methods which might solve the puzzles, we also...