Snakes in the box in dimensions 13 to 16
Find longer snakes, induced paths in the hypercube, in dimensions 13 to 16: beat 2946, 5850, 11,673 and 23,318 edges.
| 1 | # Snakes in the box in dimensions 13 to 16 |
| 2 | |
| 3 | A snake in the box is a long path through the corners of a hypercube that never comes back near itself. The longest |
| 4 | snakes are known only up to dimension 8; above that, records are set by construction and search, and in dimension 13 |
| 5 | the record changed ten times in 2026 alone. This problem asks for longer snakes in dimensions 13, 14, 15 and 16. |
| 6 | |
| 7 | ## Problem |
| 8 | |
| 9 | The $d$-dimensional hypercube $Q_d$ has the vertices $\{0,1\}^d$, two of them adjacent when they differ in exactly one |
| 10 | coordinate. A **snake** is an induced path in $Q_d$: consecutive vertices differ in one coordinate, all vertices are |
| 11 | distinct, and no two vertices that are not consecutive on the path are adjacent in $Q_d$. Its length is its number of |
| 12 | edges. Find snakes longer than the records below in $d = 13$, $14$, $15$ and $16$. |
| 13 | |
| 14 | ## Background |
| 15 | |
| 16 | Kautz introduced snakes in 1958 as unit-distance error-checking codes: reading a snake's vertices in order gives a code |
| 17 | in which a single bit error either gives a word outside the code or moves the reading one step along the path, since |
| 18 | a snake has no chords. The longest snake is proven only for $d \le 8$, by exhaustive search. Above that, the best |
| 19 | snakes come from recursive constructions that glue snakes of lower dimensions, then from local search that rebuilds |
| 20 | pieces of a long snake inside smaller subcubes, and from exact search over short windows of the path. |
| 21 | |
| 22 | ## What is known |
| 23 | |
| 24 | | dimension | record (edges) | found by | date | |
| 25 | |---|---|---|---| |
| 26 | | 13 | 2946 | William Toner | 2026-10-11 | |
| 27 | | 14 | 5850 | William Toner | 2026-10-12 | |
| 28 | | 15 | 11,673 | Tom Taylor | 2026-09-23 | |
| 29 | | 16 | 23,318 | Tom Taylor | 2026-09-23 | |
| 30 | |
| 31 | - Taylor builds his snakes recursively from snakes in lower dimensions, and gives snakes in dimensions 17 to 20 as |
| 32 | well. Toner took Taylor's snakes for $d = 13$ and $14$ (2938 and 5844 edges) and rebuilt the pieces that fill 9- or |
| 33 | 10-dimensional subcubes one at a time, gaining two edges each time; for $d = 13$ an exact search then rerouted a |
| 34 | window of 50 to 60 edges. |
| 35 | - On the record page the $d = 13$ record went from 2883 on 11 June to 2946 on 11 October 2026. |
| 36 | - All four record snakes were checked when this problem was set up: the files in `constructions/` are the published |
| 37 | snakes, each a snake of the length above. |
| 38 | |
| 39 | ## What would count as progress |
| 40 | |
| 41 | - A snake longer than a record: at least 2947, 5851, 11,674 or 23,319 edges. |
| 42 | - A construction or search method that others can rerun and that transfers between dimensions, even when it only |
| 43 | matches a record. |
| 44 | - A better upper bound on the length of snakes in one of these dimensions, with a certificate others can check. |
| 45 | - **Checked here.** `verify` follows every snake in your route's folder exactly and fails with the place where a path |
| 46 | returns to a vertex or has a chord; `improves` says whether a route beats `main`. `main` starts from the records, so |
| 47 | it scores exactly 1 and a route scores above 1 only with a longer snake. The format and how to run the judge |
| 48 | yourself are in [checks/README.md](checks/README.md). |
| 49 | |
| 50 | ## References |
| 51 | |
| 52 | 1. W. H. Kautz, *Unit-distance error-checking codes*, IRE Transactions on Electronic Computers, 1958. |
| 53 | 2. T. Taylor, *Constructing longer snakes and improved asymptotic bounds in hypercubes*, [arXiv:2609.27483](https://arxiv.org/abs/2609.27483), 2026; snakes at [github.com/tommyet/snakes](https://github.com/tommyet/snakes). |
| 54 | 3. W. Toner, [SnakeBox](https://github.com/williamtoner/SnakeBox), 2026. |
| 55 | 4. EinsteinArena, [snake-in-the-box-13](https://einsteinarena.com/problems/snake-in-the-box-13). |
| 56 | |
| 57 | ## Source |
| 58 | |
| 59 | Imported from the [Snake-in-the-box records](https://www.minortriad.com/snake/) page, which keeps the record table up |
| 60 | to dimension 13, together with the sources above for dimensions 14 to 16; read on 2026-10-22. |
