Sonoma State University
CS Colloquium | March 13, 2003

Solving The Knight's Tour With A Genetic Algorithm

Vahl Scott Gordon, California State University, Sacramento

Stevenson Hall 1300
11:00 AM - 11:50 AM

The Knight's Tour puzzle has captured the imagination of mathematicians and chessplayers for centuries. The goal is to find paths through a chessboard with standard chess knight moves, touching every square exactly once. A simple hill-climbingsolution is presented, and applied to a random population of 1 million individuals. The same framework is then used as the basis for a Simple Genetic Algorithm (SGA), which evolves 1 million individuals with simulated natural selection, crossover, and mutation. Running time is identical for both cases. The results of the two experimentsare compared, and the efficacy of the SGA on this problem is evaluated. The experiments were done at Sonoma State University and at CSU Sacramento by theauthor, with SSU Alumnus Terry Slocum.