New lower bounds for the snake-in-the-box and the coil-in-the-box problems: 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 1950s (Kautz 1958). Snake-in-the-box codes, or snakes, are open paths while coil-in-the-box codes, or coils, are closed paths, or cycles. 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.