Using Evolutionary Techniques to Hunt for Snakes and Coils

The snake-in-the-box problem is a difficult problem in mathematics and computer science that deals with finding the longest-possible constrained path that can be formed by following the edges of a multi-dimensional hypercube. This problem was first described by Kautz in the late 1950's (Kautz 1958). Snake-in-the-box codes, or `snakes, ' are the node or transition sequences of constrained open paths through an n-dimensional hypercube. Coil-in-the-box codes, or `coils, ' are the node or transition sequences of constrained closed paths, or cycles, through an ndimensional hypercube. Snakes and coils have many applications in electrical engineering, coding theory, and computer network topologies. Generally, the longer the snake or coil 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 (1) the longest-known snake in each of the dimensions nine through twelve and (2) the longestknown coil in each of the dimensions nine through eleven