用循环交集解排列谜题，高效求解TopSpin游戏
CayleyR: Solving the TopSpin puzzle via cycle intersection
- 通过双向随机搜索生成置换循环，找寻起点与终点的连接路径
- 在20步内解决12个元素的TopSpin(12,4)谜题，成功率超95%
- 适合对群论算法或谜题求解感兴趣的开发者和数学爱好者
我们提出cayleyR，一个用于通过检测凯莱图中循环交集来求解排列谜题的R语言包。核心算法采用迭代双向搜索：从初始和目标置换状态出发，随机操作序列生成对称群Sn凯莱图中的循环；其交集即为连接路径。若无直接交集，则采用距离引导的桥接选择缩小差距，过程重复进行。该软件针对TopSpin(n,k)谜题，其状态空间是由循环移位和前缀反转生成的Sn凯莱图。本文描述了数学框架、算法设计及实现，结合了基于C++哈希索引的状态存储与可选的Vulkan GPU加速。软件已公开发布于CRAN。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。