Back to projects

Lengthening hypercube snakes with windowed rerouting

I, like many people, was first introduced to the snake-in-the-box problem through xkcd #3125:

The vertices of an n-th dimensional hypercube can be labelled as n-bit strings. Then, a valid snake is a path such that the (Hamming) distance between consecutive vertices in the path is 1, and the distance between any non-consecutive vertices is at least 2. Our goal is to construct the largest snake possible for a given dimension n.

Prior work

Since the publication of the comic, longer snakes have been discovered for n greater than 8, but these constructions are not known to be optimal. Various computational approaches have been successful in lengthening snakes. On June 24, 2026, the following were the best known snakes for 9 ≤ n ≤ 13.

All of these results were constructed by improving existing solutions. Wynn's 190-length 9th dimensional snake was constructed by combining 8th dimensional snakes. Ace's 376-length 10th dimensional snake was constructed by extending a 9th dimensional snake, which itself was constructed by extending an 8th dimensional snake. Ace's 11th, 12th, and 13th dimensional snakes were constructed by priming searches with n-1 and n-2 snake seeds.

The challenge with brute-forcing the snake-in-the-box problem is the sheer size of the landscape. An n-th dimensional hypercube has 2ⁿ vertices, meaning there are (2ⁿ)! Hamiltonian paths which could contain the optimal snake as a sub-sequence. As a result, naive ILP formulations that I attempted would struggle to find valid solutions for n > 6.

Windowed rerouting

My first successful idea was to use a windowed rerouting process. We can randomly select starting and ending vertices, then attempt to find an alternative route that maintains the desired Hamming distance properties yet traverses more vertices. If such a route is found, we can splice it into the snake and continue searching.

A couple of the implementation details were particularly useful: the search algorithm used to find reroutes uses DFS with candidates evaluated in ascending Warnsdorff order, a heuristic most well-known for its use in the Knight's Tour problem. In effect, this prioritizes searching easier, faster regions.

In practice, I was able to find a total of four helpful reroutes for current best-known snakes with 9 ≤ for n ≤ 13: three longer reroutes in Ace's 2892-length 13th dimensional snake and one longer reroute in Ace's 1461-length 12th dimensional snake. Note that the layout in the below diagrams was chosen to minimize visual overlaps; the images do not represent the actual problem geometry.

12th-dimensional snake (1461 → 1463)

From the original segment of 17 vertices, 10 of them are preserved in the longer reroute. These 10 vertices constitute 3 static clusters: "f89-f8d-f9d-fdd-fdc", "f4f-fcf-fcb", and "fda-f9a".

In the diagram below, the black arrows represent the original path, and the blue arrows represent the longer reroute; blue outlined nodes represent vertices not present in the original path. Vertices are denoted by the hexadecimal equivalent of their n-bit strings.

13-th dimensional snake (2892 → 2898)

As previously mentioned, there are three different windows in the 2892-length snake which could be rerouted into longer paths. Each increases the snake length by 2.

Starting from "62":

Starting from "1e28":

Finally, starting from "1e51":

Results

The final results of this method are slightly longer 12th and 13th dimensional snakes. But, only the 13th dimensional snake is a best-known length as of the time of writing: Ace managed to produce a longer, 1465-length 12-dimensional snake around the same time.

^†As of the time of writing, on June 26, 2026.

I also want to thank Tom Ace of https://www.minortriad.com for his helpful correspondence and his website, which tracks best-known results for snake-in-the-box and related (symmetric) coil-in-the-box problems.

Last updated June 26, 2026