🔢 mathematics

A Census of New Snake-in-the-Box Records

This paper presents new, longer induced paths (snakes) in hypercube graphs for dimensions 9 through 13, thereby improving the known lower bounds for the snake-in-the-box problem and providing a computer-verifiable dataset of these record-length paths.

Original authors: Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov

Published 2026-07-17

📖 3 min read🧠 Deep dive

CC BY 4.0

Original authors: Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to navigate a giant, multi-dimensional maze made entirely of light switches. In this world, every room is a unique combination of switches being either "on" or "off." To move from one room to the next, you can only flip exactly one switch. This is the "hypercube," a shape that exists in math but feels like a digital labyrinth. Now, imagine you want to walk through as many rooms as possible without ever stepping into a room you've already visited, and with a special rule: you can't take a shortcut. If you are in Room A and Room B, and they are both connected to Room C, you can't jump from A to B just because they are neighbors; you must follow the path you started. This specific kind of walk is called a "snake."

Why does anyone care about these digital snakes? It turns out that finding the longest possible snake in these mazes is crucial for building better error-detecting codes. Think of these codes as the safety nets that keep your text messages, satellite signals, and computer data from getting garbled when they travel through the noisy universe. The longer the snake, the more robust the code can be. For decades, mathematicians have been racing to find the longest possible snake for mazes of different sizes, but for the larger, more complex mazes, the record has been stuck for a long time.

This paper is a major update to that race. The authors, a team of researchers, have used powerful computers to find new, longer snakes in mazes of dimensions 9 through 13. Before this work, the best-known snakes in these dimensions were the longest anyone had ever seen. The team didn't just find one or two; they found significantly longer paths, breaking the previous records in every single dimension they tested. For example, in a 9-dimensional maze, they found a snake with 191 steps, beating the old record of 190. In the massive 13-dimensional maze, they pushed the length to 2,922 steps, surpassing the previous best of 2,900.

The researchers didn't just stop at finding one path; they acted like digital archaeologists, digging up entire families of these record-breaking snakes. In the 9-dimensional case, they discovered 1,311 distinct ways to build a snake of that new record length. They also applied their methods to find longer "coils" (which are like snakes that loop back to the start) and "symmetric coils" (where the second half of the loop mirrors the first). Their results show that the previous limits were not the true ceiling; there is still more room to grow. All of these new, longer paths have been saved in a public dataset, allowing anyone to verify the math or use these new, longer paths to build even better error-detecting codes. While they haven't solved the puzzle for every possible dimension, they have successfully extended the known boundaries of what is possible in the digital maze, proving that with enough computational power, we can still find new, longer ways to walk through the dark.

Technical Summary: A Census of New Snake-in-the-Box Records

Problem Definition
The paper addresses the "snake-in-the-box" problem, originally formulated by Kautz in 1958 in the context of error-detecting codes. The problem seeks the longest induced (chordless) path, termed a "snake," within the hypercube graph $Q_n$ . In $Q_n$ , vertices represent binary strings of length $n$ , and edges connect strings differing in exactly one coordinate. A snake is defined as a sequence of distinct vertices where consecutive vertices are adjacent, and no two non-consecutive vertices are adjacent. The maximum length of such a path is denoted as $a(n)$ .

The paper also considers related structures: "coils" (induced cycles in $Q_n$ ) with maximum length $b(n)$ , and "symmetric coils" (coils where the second half of the cycle mirrors the first half via a fixed XOR operation), with maximum length $c(n)$ . While exact values for $a(n)$ and $b(n)$ are known for dimensions $n \le 8$ , and $c(n)$ is known for $n \le 7$ , the problem remains unsolved for $n \ge 9$ (and $n \ge 8$ for symmetric coils), where only lower bounds have been established through various computational searches.

Methodology and Approach
The authors employ sustained computational efforts to search for longer snakes, coils, and symmetric coils in dimensions 9 through 13. The paper does not detail a specific novel algorithmic architecture in the text provided but positions its work as an advancement over previous methods, which have included genetic algorithms, population-based evolutionary searches, permutation-based constructions, and Monte-Carlo tree searches.

The authors' approach focuses on generating and verifying record-length paths. They utilize a standard notation where a snake is represented by a transition sequence—the ordered list of 0-indexed coordinate indices flipped along the path. To ensure the validity of their findings, the authors provide a computer-verifiable dataset. They also perform a census of the solution space, counting the number of inequivalent snakes found at record lengths. Equivalence is determined by the symmetries of $Q_n$ , which include $n!$ coordinate permutations, $2^n$ translations (XORing), and path reversal.

Key Contributions and Results
The primary contribution of the paper is the establishment of new lower bounds for $a(n)$ , $b(n)$ , and $c(n)$ in dimensions 9 through 13, surpassing all previously known records.

Snake Lengths ( $a(n)$ ): The authors present snakes longer than the previous best-known in every dimension from 9 to 13.
- $n=9$ : A new length of 191 (improving the previous 190). The authors identified 1,311 inequivalent snakes of this length.
- $n=10$ : A new length of 379 (improving the previous 376).
- $n=11$ : A new length of 746 (improving the previous 737).
- $n=12$ : A new length of 1,476 (improving the previous 1,465).
- $n=13$ : A new length of 2,922 (improving the previous 2,900).
- The improvements range from +1 to +22 over previous records.
Coil Lengths ( $b(n)$ ): The paper reports improved lower bounds for the longest coils in dimensions 9, 10, and 11, with new lengths of 192, 374, and 732, respectively.
Symmetric Coil Lengths ( $c(n)$ ): Improved lower bounds are provided for dimensions 10 and 11, with new lengths of 370 and 726.

The authors provide a concrete example of a length-191 snake in $Q_9$ , listing its full transition sequence. They note that among millions of sampled length-191 snakes, exactly 131 symmetry classes were found for $n=9$ , leading to a conjecture that no other classes exist, though they make no such completeness claim for $n \ge 10$ .

Significance and Claims
The paper claims significance primarily through the empirical advancement of the known bounds for the snake-in-the-box problem. By providing snakes that are strictly longer than any previously known in dimensions 9 through 13, the authors have tightened the lower bounds on the maximum possible length of induced paths in hypercubes.

The work serves as a "census" of these new records, offering a comprehensive dataset that includes the specific transition sequences for all distinct record-length snakes found. This dataset is made publicly available in a computer-verifiable format, allowing for independent verification of the results. The authors frame their work as a continuation of the computational lineage established by previous researchers (such as Ace, Echols, Meyerson, and others), pushing the frontier of what is computationally achievable in this combinatorial optimization problem without claiming to have solved the problem for these dimensions or to have proven the optimality of their new bounds.

Technical Summary: A Census of New Snake-in-the-Box Records

More like this