Using Evolutionary Techniques to Hunt for Snakes and Coils

Abstract

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 multidimensional 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 n-dimensional 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 longest-known coil in each of the dimensions nine through eleven.