New Lower Bounds for the Snake-In-The-Box Problem: Using Evolutionary Techniques to Hunt for Snakes

Abstract

The snake-in-the-box problem is a difficult problem in mathematics and computer science that was first described by Kautz in the late 1950’s (Kautz 1958). Snake-in-the-box codes have many applications in electrical engineering, coding theory, and computer network topologies. Generally, the longer the snake for a given dimension, the more useful it is in these applications (Klee 1970). By applying a relatively recent evolutionary search algorithm known as a population-based stochastic hill-climber, new lower bounds were achieved for the longest snake in each of the dimensions nine through twelve and the longest coil in each of the dimensions nine through eleven.