Snake-In-The-Box Codes for Dimension $7$

Abstract

In the $n$-dimensional hypercube, an $n$-snake is a simple path with no chords, while an $n$-coil is a simple cycle without chords. There has been much interest in determining the length of a maximum $n$-snake and a maximum $n$-coil. Only upper and lower bounds for these maximum lengths are known for arbitrary $n$. Computationally, the problem of finding maximum $n$-snakes and $n$-coils suffers from combinatorial explosion, in that the size of the solution space which must be searched grows very rapidly as $n$ increases. Previously, the maximum lengths of $n$-snakes and $n$-coils have been established only for $n\le 7$and $n\le 6$, respectively. In this paper, we report on a coil searching computer program which established that $48$ is the maximum length of a coil in the hypercube of dimension $7$.