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. 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's been marked unusable.

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 cycles in hypercubes, called the coil-in-the-box problem.

The snake-in-the-box problem was first described by harvtxt|Kautz|1958, 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.

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 OEIS|id=A099155.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:97, 188, 363, 680, 1260.

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 OEIS|id=A000937.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, 180, 344, 630, 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. However the constant of proportionality is not known. [For asymptotic lower bounds, see harvtxt|Evdokimov|1961, harvtxt|Wojciechowski|1989, and harvtxt|Abbot|Katchalski|1991. For upper bounds, see harvtxt|Douglas|1969, harvtxt|Deimer|1985, harvtxt|Solov'eva|1987, harvtxt|Abbot|Katchalski|1988, harvtxt|Snevily|1994, and harvtxt|Zémor|1997.]

Notes

References

*citation
last1 = Abbot | first1 = H. L.
last2 = Katchalski | first2 = M.
title = On the snake in the box problem
journal = Journal of Combinatorial Theory, Series B
volume = 44
pages = 12–24
year = 1988.

*citation
last1 = Abbot | first1 = H. L.
last2 = Katchalski | first2 = M.
title = On the construction of snake-in-the-box codes
journal = Utilitas Mathematica
volume = 40
year = 1991
pages = 97–116.

*citation
last = Bitterman | first = D. S.
title = New Lower Bounds for the Snake-In-The-Box Problem: A Prolog Genetic Algorithm and Heuristic Search Approach
series = MSAI thesis
publisher = Univ. of Georgia
date = 2004
url = http://www.cs.uga.edu/~potter/CompIntell/bitterman_derrick_s_200412_ms.pdf.

*citation
last1 = Blaum | first1 = Mario | last2 = Etzion | first2 = Tuvi
title = Use of snake-in-the-box codes for reliable identification of tracks in servo fields of a disk drive
year = 2002
id = US patent|6496312.

*citation
last1 = Casella | first1 = D. A. | last2 = Potter | first2 = W. D.
contribution = Using Evolutionary Techniques to Hunt for Snakes and Coils
title = 2005 IEEE Congress on Evolutionary Computation (CEC2005)
volume = 3
pages = 2499–2504
date = 2005.

*citation
last = Casella | first = D. A.
title = New Lower Bounds for the Snake-in-the-Box and the Coil-in-the-Box Problems
version = MSAI thesis
publisher = Univ. of Georgia
date = 2005
url = http://www.cs.uga.edu/~potter/CompIntell/casella_darren_a_200505_ms.pdf.

*citation
last1 = Danzer | first1 = L. | last2 = Klee | first2 = V.
title = Length of snakes in boxes
journal = Journal of Combinatorial Theory
volume = 2
pages = 258–265
year = 1967
doi = 10.1016/S0021-9800(67)80026-7.

*citation
last = Davies
title = Longest 'separated' paths and loops in an "N"-cube
journal = IEEE Trans. Electron. Comput.
volume = EC-14
year = 1965
pages = 261
doi = 10.1109/PGEC.1965.264262
first = D. W..

*citation
last = Deimer | first = Knut
title = A new upper bound for the length of snakes
journal = Combinatorica
volume = 5
year = 1985
issue = 2
pages = 109–120
doi = 10.1007/BF02579373.

*citation
last = Douglas | first = Robert J.
title = Upper bounds on the length of circuits of even spread in the "d"-cube
journal = J. Combinatorial Theory
volume = 7
year = 1969
pages = 206–214
doi = 10.1016/S0021-9800(69)80013-X.

*citation
last = Evdokimov | first = A. A.
title = Maximal length of a chain in a unit "n"-dimensional cube
journal = Mat. Zametki
volume = 6
pages = 309–319
year = 1969.

*citation
last = Kautz | first = W. H.
title = Unit-distance error-checking codes
journal = IRE Trans. Elect. Comput.
volume = 7
pages = 177–180
year = 1958.

*citation
last1 = Kim | first1 = S. | last2 = Neuhoff | first2 = D. L.
contribution = Snake-in-the-box codes as robust quantizer index assignments
date = 2000
title = Proceedings of the IEEE International Symposium on Information Theory
pages = 402
doi = 10.1109/ISIT.2000.866700.

*citation
last = Klee | first = V.
title = What is the maximum length of a "d"-dimensional snake?
journal = American Mathematical Monthly
volume = 77
pages = 63–65
year = 1970
doi = 10.2307/2316860.

*citation
last = Kochut | first = K. J.
title = Snake-in-the-box codes for dimension 7
journal = Journal of Combinatorial Mathematics and Combinatorial Computing
volume = 20
pages = 175–185
year = 1996.

*citation
last1 = Lukito | first1 = A. | last2 = van Zanten | first2 = A. J.
title = A new non-asymptotic upper bound for snake-in-the-box codes
journal = Journal of Combinatorial Mathematics and Combinatorial Computing
volume = 39
year = 2001
pages = 147–156.

*citation
last1 = Paterson | first1 = Kenneth G. | last2 = Tuliani | first2 = Jonathan
title = Some new circuit codes
journal = IEEE Trans. Inform. Theory
volume = 44
year = 1998
issue = 3
pages = 1305–1309
doi = 10.1109/18.669420.

*cite conference
author = Potter, W. D.; Robinson, R. W.; Miller, J. A.; Kochut, K. J.; Redys, D. Z.
title = Using the genetic algorithm to find snake in the box codes
booktitle = Proceedings of the Seventh International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems, Austin, Texas
pages = 421–426
date = 1994

*citation
last = Snevily | first = H. S.
title = The snake-in-the-box problem: a new upper bound
journal = Discrete Mathematics
volume = 133
pages = 307–314
year = 1994
doi = 10.1016/0012-365X(94)90039-6.

*citation
last = Solov'eva | first = F. I.
title = An upper bound on the length of a cycle in an "n"-dimensional unit cube
journal = Metody Diskret. Analiz.
volume = 45
year = 1987
pages = 71–76 and 96–97 (In Russian).

*cite conference
author = Tuohy, D.R.; Potter, W.D.; Casella, D.A.
title = Searching for Snake-in-the-Box Codes with Evolved Pruning Models
booktitle = Proceedings of the 2007 Int. Conf. on Genetic and Evolutionary Methods (GEM'2007), Las Vegas, Nevada
pages = 3-9
date = 2007

*citation
last = Wojciechowski | first = J.
title = A new lower bound for snake-in-the-box codes
journal = Combinatorica | volume = 9 | year = 1989 | issue = 1 | pages = 91–99
doi = 10.1007/BF02122688.

*cite journal
author = Yang, Yuan Sheng; Sun, Fang; Han, Song
title = A backward search algorithm for the snake in the box problem
journal = J. Dalian Univ. Technol.
volume = 40
year = 2000
issue = 5
pages = 509–511

*citation
last = Zémor | first = Gilles
title = An upper bound on the size of the snake-in-the-box
journal = Combinatorica
volume = 17
year = 1997
issue = 2
pages = 287–298
doi = 10.1007/BF01200911.

*citation
title = Computing binary combinatorial gray codes via exhaustive search with SAT solvers
last1 = Zinovik | first1 = I.
last2 = Kroening | first2 = D.
last3 = Chebiryak | first3 = Y.
journal = IEEE Transactions on Information Theory
volume = 54 | issue = 4 | year = 2008 | pages = 1819–1823
doi = 10.1109/TIT.2008.917695.

External links

*cite web
author = Potter, W. D.
url = http://www.cs.uga.edu/~potter/SnakeRecords.html
year = 2006
title = Current Records for the Snake-in-the-Box Problem

*mathworld | title = Snake | urlname = Snake