Snake-in-the-box
The snake-in-the-box problem in and computer science deals with finding a certain kind of path along the edges of a . This path starts at one corner and travels along the edges to as many corners as it can reach. After it gets to a new corner, the previous corner and all of its neighbors must be marked as unusable. The path should never travel to a corner after it has been marked unusable.
In other words, a snake is a connected open path in the hypercube where each node in the path, with the exception of the head (start) and the tail (finish), has exactly two neighbors that are also in the snake. The head and the tail each have only one neighbor in the snake. The rule for generating a snake is that a node in the hypercube may be visited if it is connected to the current node and it is not a neighbor of any previously visited node in the snake, other than the current node.
In graph theory terminology, this is called finding the longest possible in a ; it can be viewed as a special case of the . There is a similar problem of finding long induced in hypercubes, called the coil-in-the-box problem.
The snake-in-the-box problem was first described by , motivated by the theory of . The vertices of a solution to the snake or coil in the box problems can be used as a that can detect single-bit errors. Such codes have applications in , coding theory, and computer . In these applications, it is important to devise as long a code as is possible for a given dimension of hypercube. The longer the code, the more effective are its capabilities.
Finding the longest snake or coil becomes notoriously difficult as the dimension number increases and the search space suffers a serious . Some techniques for determining the upper and lower bounds for the snake-in-the-box problem include proofs using and , of the search space, and search utilizing evolutionary techniques.
Known lengths and bounds
The maximum length for the snake-in-the-box problem is known for dimensions one through eight; it is
- 1, 2, 4, 7, 13, 26, 50, 98 .
Beyond that length, the exact length of the longest snake is not known; the best lengths found so far for dimensions nine through thirteen are
- 190, 370, 708, 1357, 2687.
For cycles (the coil-in-the-box problem), a cycle cannot exist in a hypercube of dimension less than two. Starting at that dimension, the lengths of the longest possible cycles are
- 4, 6, 8, 14, 26, 48, 96 .
Beyond that length, the exact length of the longest cycle is not known; the best lengths found so far for dimensions nine through thirteen are
- 188, 358, 668, 1340, 2584.
Doubled coils are a special case: cycles whose second half repeats the structure of their first half, also known as symmetric coils. For dimensions two through seven the lengths of the longest possible doubled coils are
- 4, 6, 8, 14, 26, 46.
Beyond that, the best lengths found so far for dimensions eight through thirteen are
- 94, 186, 362, 662, 1222, 2354.
For both the snake and the coil in the box problems, it is known that the maximum length is proportional to 2n for an n-dimensional box, asymptotically as n grows large, and bounded above by 2n-1. However the constant of proportionality is not known, but is observed to be in the range 0.3 – 0.4 for current best known values.