Improve the best-known longest snake (snake-in-the-box) in the 9-dimensional hypercube beyond length 190
Statement
A snake (snake-in-the-box) in the hypercube graph $Q_n$ is an induced (chordless) simple path: a sequence of distinct vertices in $\{0,1\}^n$, consecutive vertices differing in exactly one bit, such that no two non-consecutive vertices of the path are adjacent in $Q_n$. Its length is the number of edges. Let $\lambda(n)$ be the maximum snake length in $Q_n$. Exact values are known only for $n \le 8$: $\lambda(8)=98$. For $n=9$ the exact maximum is open; the best known snake has length 190. Exhibit an induced path in $Q_9$ of length at least 191, improving the lower bound on $\lambda(9)$.
Acceptance. FULLY (advances the frontier): an induced path in $Q_9$ of length $\ge 191$ - given as the ordered vertex list (or the sequence of bit-flip transitions) - verified by checking (i) all vertices are distinct, (ii) consecutive vertices differ in exactly one bit, and (iii) no two non-consecutive vertices are at Hamming distance 1. This raises the lower bound on $\lambda(9)$. FULLY RESOLVES: additionally, a proof that $\lambda(9)$ equals the exhibited value (matching upper bound). PARTIAL: a snake matching the current record (190) via an independent construction. Provide the transition sequence and a verifier.
Background
The snake-in-the-box problem (Kautz, 1958) concerns error-detecting Gray-type codes and is a classic hard combinatorial search problem. Maximal snakes are proven optimal only for $n \le 8$ (values $1,2,4,7,13,26,50,98$); the $n=8$ optimum 98 was established via exhaustive search (Ostergard & Pettersson). For $n=9$ only lower bounds are known; the best-known length 190 is from Wynn, 'Constructing circuit codes by permuting initial sequences' (2012, arXiv:1201.1647). Subsequent heuristic searches (evolutionary/beam-search methods; e.g. Meyerson et al., 'Finding Longest Paths in Hypercubes: 11 New Lower Bounds', 2015; and QUBO/annealing formulations, arXiv:2409.04476) improved records in higher dimensions, but the $n=9$ record has proven stubborn. Source: the Wikipedia 'Snake-in-the-box' summary table of best-known snakes and coils.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Wynn, Constructing circuit codes by permuting initial sequences (2012) | link |
| REF-02 | Snake-in-the-box (summary table of best-known snakes and coils) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.