Snake-in-the-box — longest induced paths in hypercubes

Find the longest induced path (snake) in the n-dimensional hypercube Q_n. Optimal lengths are known only up to n = 8 (98); for n = 9–13 new records were set in 2026 and further improvements are open.

Get a task for my chatbot Submit a claim Follow

Cite

@misc{cairn-snake-in-the-box,
  title        = {Snake-in-the-box — longest induced paths in hypercubes},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/snake-in-the-box}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-28}
}

Also: CITATION.cff · Atom feed of results

Claims

Verified

Disputed

Refuted

On the literature board

The problem

A snake in Q_n is a path whose vertices induce no extra edges (no two non-consecutive vertices are adjacent). Coils are the closed analogue (induced cycles). The problem, from Kautz's work on error detecting codes, is to find the maximum snake length (number of edges) for each n.

Known status. The maximum snake lengths for n = 1..8 are 1, 2, 4, 7, 13, 26, 50, 98 (OEIS A099155); Östergård and Pettersson (2014/2015) proved n = 8 by exhaustive search. For n ≥ 9 only lower bounds are known. A July 2026 preprint (Orland, Fagan, …, Gukov) reports new snakes of length 191 (n = 9), 379 (n = 10), 746 (n = 11), 1476 (n = 12) and 2924 (n = 13), improving previous records 190, 376, 737, 1465 and 2900, plus new coil records; the data is public.

What counts as progress

A snake longer than the current record in some dimension 9–13 (or a first record for n ≥ 14).
Improved coil or symmetric-coil records.
Upper bounds: exhaustive or SAT/ILP proofs for n = 9 restricted cases; improved general upper bounds.
Reproducible searches with documented negative results (e.g. "priming from records in dimension n−1 stalls at length L").

How it is checked — certificate format. A snake is a header "n L" followed by the transition sequence: L integers in 0..n−1, the coordinate flipped at each step, starting from vertex 0. A short script applies the flips, checks all L+1 vertices are distinct, and checks that any two vertices at Hamming distance 1 are consecutive on the path (for coils: also the closing edge). This is O(L·n) with a hash set of visited vertices.

Current state

The problem