Building symmetric coils with implicit-quotient beam search

Before the improvements described here, the following were the best known lengths for the snake-in-the-box, coil-in-the-box, and symmetric coil-in-the-box problems, in dimensions 9 ≤ n ≤ 13: (sourced from www.minortriad.com)

Baseline best lengths, as of July 1, 2026
n	snake	coil	symmetric coil
9	190	188	186
10	376	370	362
11	737	728	674
12	1465	1442	1222
13	2898	2832	2354

In dimensions n ≤ 10, the longest known symmetric coils are approximately the same length as the longest known snakes and coils. After the 10th dimension, the lengths of the best-known constructions for these problems deviate significantly, as shown by the percentage of best-known symmetric coil versus best-known (general) coil:

Symmetric-to-generic coil length percentage
n	(previous-best symmetric coil) / (best-known coil)
7	95.8% (46/48)
8	97.9% (94/96)
9	98.9% (186/188)
10	97.8% (362/370)
11	92.6% (674/728)
12	84.7% (1222/1442)
13	83.1% (2354/2832)

For n ≤ 6, proven optimal coils and symmetric coils have the same length. Experimentally, several of the best-known symmetric coils are exactly length 2 shorter than best-known general coils; this is the case in dimensions 7, 8, and 9.

Findings

Given the unexplained percentage decrease and structural potential of symmetric coils, I investigated approaches to build larger explicit constructions. Using an implicit-quotient beam search, I improved the best known symmetric-coil lengths in dimensions 11, 12, and 13.

New symmetric hypercube coils
n	previous-best length	new coil length	% of general coil
11	674	718	92.6% → 98.6%
12	1222	1422	84.7% → 98.6%
13	2354	2766	83.1% → 97.7%

Notably, the lengths of these symmetric coils are approximately 97-98% of the length of the best-known general coils in their dimensions, which aligns with previous empirical results for smaller n.

Implicit-quotient beam search

The vertices of the n-cube $Q_{n}$ can be naturally labelled with the vectors of $F_{2}^{n}$ . For the sake of simplicity, I will refer to vertices by their vector label. Two vertices $x, y \in F_{2}^{n}$ are adjacent if $w_{H} (x + y) = 1$ where $w_{H}$ denotes Hamming weight. We denote the neighbors of a vertex $u$ as $N (u) = {v : w_{H} (u + v) = 1}$ . A symmetric coil $C_{S} = (v_{0}, v_{1}, \dots, v_{2 m - 1}, v_{0})$ is an induced cycle over $F_{2}^{n}$ such that $\forall i \in {0,1, \dots, m - 1}, v_{i + m} = v_{i} + d$ for some fixed $d \in F_{2}^{n}$ . If $v_{i}$ and $v_{i + 1}$ are consecutive vectors in $C_{S}$ , then $w_{H} (v_{i} + v_{i + 1}) = 1$ . If $v_{i}$ and $v_{j}$ are non-consecutive vectors in $C_{S}$ , then $w_{H} (v_{i} + v_{j}) \geq 2$ .

The key symmetry is translation by $d$ : each vertex $x$ is naturally paired with $x + d$ . This gives an order-2 symmetry group $G = {id, x \mapsto x + d}$ acting on the $n$ -cube. Rather than search the full cube, we search modulo this symmetry, so vertices are treated as orbit pairs, with the goal of finding a long half-path $v_{0}, v_{1}, \dots, v_{m - 1}$ such that $w_{H} (v_{m - 1} + d) = 1$ . This quotient perspective is closely related to Wynn's work on permuted circuit codes.

Conceptually, we want to choose $d$ such that $w_{H} (d)$ is small in order to minimize interference between halves. In fact, the smallest valid weight is 3 to construct a symmetric coil with length longer than 4. The actual coordinates set to 1 are arbitrary, as any $d$ with equivalent weight is equivalent up to relabeling.

For the actual search algorithm targeting the $n$ -cube, we warm-start with the first $k$ transitions from the half-sequence of an existing $(n-1)$ -symmetric coil. Priming the search with lower-dimensional seeds is a strategy adapted from Ace's recent record constructions for snakes and coils. By convention, $v_{0} = 0$ . Then, we build a blocked bitmap of invalid vertices and set the head to the last vertex of the seeded path.

Along with each candidate $u$ , the algorithm also considers its pair for the second-half $u + d$ . In particular, if a candidate $u$ is chosen to follow to the current head $h$ , then all of the following must be blocked: $N (h), u, u + d, N (u + d)$ . Closure is determined when the chosen candidate $u$ satisfies $w_{H} (u + d) = 1$ . Candidates are evaluated from $N (h)$ using a beam search. Saved states for the beam are determined by a heuristic which attempts to minimize the number of new forbidden vertices (and thus maximally "reuse" the existing blocked vertices) with a bias to keep eventual traversal to $d$ possible.

Using this method, the symmetric coils presented under Findings were generated with relatively small RAM usage (< 4GB) with a cumulative computation time under 2 hours on an Intel i5-10600k. Beginning with a 362-length 10-d symmetric coil from Meyerson et al., we built our 11-d symmetric coil, which then seeded our 12-d symmetric coil, which then seeded our 13-d symmetric coil. Meyerson et al.'s 10-d symmetric coil used $d = e_{3} + e_{5} + e_{9}$ which we inherited for each of our results.

References

Meyerson, S.J., Drapela, T.E., Whiteside, W.E., Potter, W.D., "Finding Longest Paths in Hypercubes, 11 New Lower Bounds: Snake, Coils, and Symmetric Coils", Proceedings of the 28th Industrial, Engineering and Other Applications of Applied Intelligent Systems, LNAI-9101: Current Approaches in Applied Artificial Intelligence, Springer International, pp. 23-32.
E. Wynn, "Constructing circuit codes by permuting initial sequences", arXiv:1201.1647v1 (2012).
Ace, T. (2026). "Priming Snake-in-the-Box Search with Seed Snakes in n-1 and n-2 Dimensions," Zenodo. doi:10.5281/zenodo.20753867

Last updated July 2, 2026