Snake-in-the-box research page

The Snake-in-the-box problem is a hard search/optimization problem, first described over 50 years ago, that seeks longest chord-free (self-avoiding) paths in n-dimensional hypercube graphs ( description at Wikipedia). Open paths are "snakes", closed paths are "coils". An interesting special case is "symmetric coils", whose second half repeats the sequence of transitions occurring in their first half. Optimal solutions are known only for dimensions n <= 7, and it's been estimated that an exhaustive search for solutions in dimension 8 would take many years of 2011 CPU time. As n increases beyond 7 the SITB problem gets much harder very quickly, as the search space size is O(n^(2^n)).

The SITB problem is of more than academic interest, as it has many significant applications. Among these are:

• Error detecting circuit codes, such as disk sector codes resistant to 1 bit read errors
• Coding schemes for Analogue to Digital converters
• Electronic locks
• Rank modulation schemes for charge distribution in modern multi-level flash memories
• Finding stable periodic orbits that describe gene activation sequences in embryonic development!!

It's fascinating that such a conceptually simple problem has a direct application in embryology.

Early approaches were mainly based on Depth-First Search (DFS) with safe pruning heuristics. Below is a table of the known lengths of optimal (longest maximal) snakes, coils and symmetric coils for dimensions 2 to 7. These optima were proven by exhaustive search.

Dimension	Longest snake	Longest coil	Longest sym. coil
2	2	4	4
3	4	6	6
4	7	8	8
5	13	14	14
6	26	26	26
7	50	48	46

The state-of-the-art in finding best known (but usually not optimal) solutions for n > 7 has, until very recently, been Evolutionary Computation (EC) approaches such as Genetic Algorithms (GAs). EC approaches have also been applied indirectly to learn good pruning heuristics to make DFS more tractable. Most recent coil records, however, were found by a clever constructive technique based on permutations combined with DFS.

I first learned of the problem from a presentation at GECCO 2010 (a fabulous conference!) where a long standing record of 97 for dimension 8 was broken by a 98 edge snake found by a GA. Intrigued, this year I've been developing and applying some non-evolutionary approaches with a great deal of recent success - breaking the snake records for dimensions 10, 11, and 12, and symmetric coil records in dimensions 8 and 9 (subsequently eclipsed) and 10, 11 and 12. Below are previous records (held by others) and my latest results (updated Feb. 16th 2012) for dimensions 8 to 12.
The old record of 86 for a symmetric coil in dimension 8 apparently stood for 38 years before I broke it last December with a 90, and just 1 month later it was broken again by Ed Wynn with a 94, which is optimal. The other current records for dimension 8 are also probably (but not proven to be) optimal, and those in dimension 9 are somewhat close to optimal, but those in higher dimensions are definitely sub-optimal. Please send me email if you break any of these records!

Dimension	Previous best snake	New best snake	Previous best coil	New best coil	Previous best sym-coil	New best sym-coil
8	98 optimal?	-	96 optimal?	-	94 optimal	-
9	190	-	188	-	170	180
10	363	370	348	-	294	348
11	680	695	640	-	494	640
12	1260	1274	1238	-	902	1128

• Don Potter's SITB records page at the University of Georgia's Institute for AI
• W. Kautz. Unit-distance error-checking codes. IRE Transactions on Electronic Computers 7, 1958.
• H. Snevily. The snake-in-the-box problem: A new upper bound. Discrete Mathematics 133, 1994.
• K. Kochut. Snake-in-the-box codes for dimension 7. Combinatorial Mathematics and Combinatorial Computations 20, 1996.
• D. Tuohy et al. Searching for Snake-in-the-Box Codes with Evolved Pruning Models. Proc. AAAI, 2007.
• L. Adelson et al. Long Snakes and a Characterisation of Maximal Snakes on the d-cube. Proc. 4th S-E Conf. Combinatorics, Graph Theory and Computing, 1973.