Snake-in-the-box
Encyclopedia
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
. 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
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 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
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 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.
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...
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 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.