CayleyR: Solving the TopSpin puzzle via cycle intersection
arXiv:2607.13219
The paper introduces cayleyR, an R package that solves permutation puzzles such as TopSpin by using an iterative bidirectional search to find intersecting cycles in Cayley graphs, with optional GPU acceleration for speed.
Abstract
We present cayleyR, an R package for solving permutation puzzles by detecting cycle intersections in Cayley graphs. The core algorithm performs an iterative bidirectional search: from both the initial and target permutation states, random operation sequences generate cycles in the Cayley graph of the symmetric group Sn; their intersection yields a connecting path. When no direct intersection is found, a distance-guided bridge selection narrows the gap, and the process repeats. The package targets the TopSpin(n,k) puzzle, whose state space is a Cayley graph of Sn generated by a cyclic shift and a prefix reversal. We describe the mathematical framework, the algorithm, and its implementation, which combines a C++ hash-indexed state store with optional Vulkan GPU acceleration. The software is publicly available on CRAN.
17 pages, 2 figures