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)

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:

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.

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 $\mathbb{F}_2^n$. For the sake of simplicity, I will refer to vertices by their vector label. Two vertices $x, y \in \mathbb{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, \ldots, v_{2m-1}, v_0)$ is an induced cycle over $\mathbb{F}_2^n$ such that $\forall i \in \{0, 1, \ldots, m-1\}, v_{i+m} = v_i + d$ for some fixed $d \in \mathbb{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 = \{\mathrm{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, \ldots, 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 = \mathbb{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