Snake-in-the-box

Encyclopedia

The

and computer science

deals with finding a certain kind of path along the edges of a hypercube

. 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

In graph theory terminology, this is called finding the longest possible induced path

in a hypercube; it can be viewed as a special case of the induced subgraph isomorphism problem

. There is a similar problem of finding long induced cycle

s in hypercubes, called the

The snake-in-the-box problem was first described by , motivated by the theory of error-correcting codes. 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. Such codes have applications in electrical engineering

, coding theory

, and computer network topologies

. 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 combinatorial explosion

. Some techniques for determining the upper and lower bounds for the snake-in-the-box problem include proofs using discrete mathematics

and graph theory

, exhaustive search of the search space

, and heuristic

search utilizing evolutionary techniques.

Beyond that length, the exact length of the longest snake is not known; the best lengths found so far for dimensions eight through twelve are

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

Beyond that length, the exact length of the longest cycle is not known; the best lengths found so far for dimensions eight through twelve are

For both the snake and the coil in the box problems, it is known that the maximum length is proportional to 2

**snake-in-the-box**problem in graph theoryGraph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

and computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

deals with finding a certain kind of path along the edges of a hypercube

Hypercube

In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...

. 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 induced path

Induced path

In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the...

in a hypercube; it can be viewed as a special case of the induced subgraph isomorphism problem

Induced subgraph isomorphism problem

In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph....

. There is a similar problem of finding long induced cycle

Cycle graph

In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...

s in hypercubes, called the

**coil-in-the-box**problem.The snake-in-the-box problem was first described by , motivated by the theory of error-correcting codes. The vertices of a solution to the snake or coil in the box problems can be used as a Gray code

Gray code

The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit. It is a non-weighted code....

that can detect single-bit errors. Such codes have applications in electrical engineering

Electrical engineering

Electrical engineering is a field of engineering that generally deals with the study and application of electricity, electronics and electromagnetism. The field first became an identifiable occupation in the late nineteenth century after commercialization of the electric telegraph and electrical...

, coding theory

Coding theory

Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

, and computer network topologies

Network topology

Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....

. 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 combinatorial explosion

Combinatorial explosion

In administration and computing, a combinatorial explosion is the rapidly accelerating increase in lines of communication as organizations are added in a process...

. Some techniques for determining the upper and lower bounds for the snake-in-the-box problem include proofs using discrete mathematics

Discrete mathematics

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...

and graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, exhaustive search of the search space

Search space

Search space may refer to one of the following.*In optimization, the domain of the function to be optimized*In search algorithms of computer science, the set of all possible solutions...

, and heuristic

Heuristic

Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...

search utilizing evolutionary techniques.

## Known lengths and bounds

The maximum length for the snake-in-the-box problem is known for dimensions one through seven; it is- 1, 2, 4, 7, 13, 26, 50 .

Beyond that length, the exact length of the longest snake is not known; the best lengths found so far for dimensions eight through twelve are

- 98, 190, 367, 689, 1265.

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 .

Beyond that length, the exact length of the longest cycle is not known; the best lengths found so far for dimensions eight through twelve are

- 96, 188, 348, 640, 1238.

For both the snake and the coil in the box problems, it is known that the maximum length is proportional to 2

^{n}for an*n*-dimensional box, asymptotically as*n*grows large, and bounded above by 2^{n-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.