Snake-in-the-box

The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube.

In other words, a snake is a connected open path in the hypercube where each node connected with path, with the exception of the head (start) and the tail (finish), it has exactly two neighbors that are also in the snake.

The vertices of a solution to the snake or coil in the box problems can be used as a Gray code that can detect single-bit errors.

In these applications, it is important to devise as long a code as is possible for a given dimension of hypercube.

Finding the longest snake or coil becomes notoriously difficult as the dimension number increases and the search space suffers a serious combinatorial explosion.