CayleyR: Solving the TopSpin puzzle via cycle intersection

# CayleyR: Solving the TopSpin Puzzle via Cycle Intersection
Source: [https://arxiv.org/html/2607.13219](https://arxiv.org/html/2607.13219)
###### Abstract\.

We presentcayleyR, 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 groupSnS\_\{n\}; 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\)\(n,k\)puzzle, whose state space is a Cayley graph ofSnS\_\{n\}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\.

###### 2020 Mathematics Subject Classification:

Primary 20B40; Secondary 05C25, 68W05

## 1\.Introduction

The TopSpin puzzle consists ofnntokens arranged in a circular track together with a*turnstile*window of widthkk\. Two moves are available at each step: \(i\) a cyclic shift of the entire track by one position \(left or right\), and \(ii\) a reversal of thekktokens currently inside the turnstile\. The goal is to transform a given arrangement of tokens into a target arrangement using a finite sequence of such moves\.

Algebraically, each arrangement corresponds to a permutation in the symmetric groupSnS\_\{n\}, the two shift directions and the reversal define three generators, and the set of all reachable arrangements forms a Cayley graphΓ​\(Sn,\{L,R,X\}\)\\Gamma\(S\_\{n\},\\\{L,R,X\\\}\)\. For evenkkthe generated group is the fullSnS\_\{n\}; for oddkkit is the alternating groupAnA\_\{n\}\. Solving the puzzle is equivalent to finding a path inΓ\\Gammabetween two vertices\.

For smallnnan exhaustive breadth\-first search \(BFS\) is feasible: the Cayley graph ofSnS\_\{n\}hasn\!n\!vertices, so BFS remains practical only up to roughlyn≤10n\\leq 10\. Beyond this threshold the state space grows super\-exponentially and classical shortest\-path algorithms become intractable\. The diameter of the TopSpin Cayley graph is conjectured to beΘ​\(n2\)\\Theta\(n^\{2\}\)\[[4](https://arxiv.org/html/2607.13219#bib.bib4)\], further compounding the difficulty\.

In this paper we propose a fundamentally different strategy\. Instead of exploring the graph level by level, we*generate random cycles*emanating from both the start and target states, and search for an*intersection*between the two families of cycles\. When a shared state is detected, a path is immediately recovered by tracing each cycle chain back to its origin\. When no intersection exists after a round of sampling, the algorithm selects a pair of*bridge states*—one from each side, chosen to minimize a distance heuristic—and restarts the cycle generation from the bridges\. This iterate\-and\-bridge scheme terminates when the two expanding fronts meet\.

The principal contributions are as follows\.

1. \(1\)We introduce the*Iterative Cycle Intersection*\(ICI\) algorithm for pathfinding in Cayley graphs of permutation groups \(Section[4](https://arxiv.org/html/2607.13219#S4)\)\.
2. \(2\)We describecayleyR, an open\-source R package implementing this algorithm with a C\+\+backend, hash\-indexed state storage, and optional Vulkan GPU acceleration \(Section[5](https://arxiv.org/html/2607.13219#S5)\)\.
3. \(3\)We report computational experiments demonstrating the scalability of the approach for TopSpin\(n,k\)\(n,k\)instances withnnup to 20 \(Section[6](https://arxiv.org/html/2607.13219#S6)\)\.

The remainder of the paper is organized as follows\. Section[2](https://arxiv.org/html/2607.13219#S2)recalls the necessary algebraic and graph\-theoretic preliminaries\. Section[3](https://arxiv.org/html/2607.13219#S3)surveys related work\. Sections[4](https://arxiv.org/html/2607.13219#S4)and[5](https://arxiv.org/html/2607.13219#S5)contain the main algorithmic and software contributions\. Section[6](https://arxiv.org/html/2607.13219#S6)presents experiments, and Section[8](https://arxiv.org/html/2607.13219#S8)concludes\.

## 2\.Preliminaries

###### Definition 1\(Cayley graph\)\.

LetGGbe a group andS⊆GS\\subseteq Ga generating set withe∉Se\\notin S\. The*Cayley graph*Γ​\(G,S\)\\Gamma\(G,S\)is the directed graph with vertex setGGand an edge fromggtog​sgsfor everyg∈Gg\\in Gands∈Ss\\in S\. IfSSis closed under inverses the graph is undirected\.

###### Definition 2\(TopSpin\(n,k\)\(n,k\)puzzle\)\.

Fix integersn≥3n\\geq 3and2≤k≤n2\\leq k\\leq n\. The state space is the set of all permutations of\{1,…,n\}\\\{1,\\dots,n\\\}, identified with elements ofSnS\_\{n\}\. Three generators act on a stateσ=\(σ1,…,σn\)\\sigma=\(\\sigma\_\{1\},\\dots,\\sigma\_\{n\}\):

\(1\)L​\(σ\)\\displaystyle L\(\\sigma\)=\(σ2,σ3,…,σn,σ1\),\\displaystyle=\(\\sigma\_\{2\},\\sigma\_\{3\},\\dots,\\sigma\_\{n\},\\sigma\_\{1\}\),\(2\)R​\(σ\)\\displaystyle R\(\\sigma\)=\(σn,σ1,σ2,…,σn−1\),\\displaystyle=\(\\sigma\_\{n\},\\sigma\_\{1\},\\sigma\_\{2\},\\dots,\\sigma\_\{n\-1\}\),\(3\)Xk​\(σ\)\\displaystyle X\_\{k\}\(\\sigma\)=\(σk,σk−1,…,σ1,σk\+1,…,σn\)\.\\displaystyle=\(\\sigma\_\{k\},\\sigma\_\{k\-1\},\\dots,\\sigma\_\{1\},\\sigma\_\{k\+1\},\\dots,\\sigma\_\{n\}\)\.Note thatR=L−1R=L^\{\-1\}andXk=Xk−1X\_\{k\}=X\_\{k\}^\{\-1\}\. The TopSpin Cayley graph isΓ​\(G,\{L,R,Xk\}\)\\Gamma\(G,\\\{L,R,X\_\{k\}\\\}\)whereG=SnG=S\_\{n\}ifkkis even andG=AnG=A\_\{n\}ifkkis odd\.

###### Definition 3\(Cycle of an operation sequence\)\.

Letw=\(w1,…,wm\)w=\(w\_\{1\},\\dots,w\_\{m\}\)be a finite word over\{L,R,Xk\}\\\{L,R,X\_\{k\}\\\}and letφw=wm∘⋯∘w1\\varphi\_\{w\}=w\_\{m\}\\circ\\cdots\\circ w\_\{1\}denote the composed permutation\. Starting from a stateσ0\\sigma\_\{0\}, the*cycle*ofwwatσ0\\sigma\_\{0\}is the sequence

σ0,φw​\(σ0\),φw2​\(σ0\),…,φwc−1​\(σ0\),\\sigma\_\{0\},\\;\\varphi\_\{w\}\(\\sigma\_\{0\}\),\\;\\varphi\_\{w\}^\{2\}\(\\sigma\_\{0\}\),\\;\\dots,\\;\\varphi\_\{w\}^\{c\-1\}\(\\sigma\_\{0\}\),wherec=ord​\(φw\)c=\\mathrm\{ord\}\(\\varphi\_\{w\}\)is the order ofφw\\varphi\_\{w\}inGG, i\.e\. the smallest positive integer withφwc=e\\varphi\_\{w\}^\{c\}=e\. The integerccis the*cycle length*\. BecauseGGis finite, this sequence is periodic and returns toσ0\\sigma\_\{0\}after exactlyccapplications ofφw\\varphi\_\{w\}\.

###### Definition 5\(Distance functions\)\.

For two permutationsσ,τ∈Sn\\sigma,\\tau\\in S\_\{n\}we use two distance heuristics\.

- •*Manhattan distance*:dM​\(σ,τ\)=∑i=1n\|σi−τi\|d\_\{M\}\(\\sigma,\\tau\)=\\sum\_\{i=1\}^\{n\}\|\\sigma\_\{i\}\-\\tau\_\{i\}\|\.
- •*Breakpoint distance*: letπ=τ−1​σ\\pi=\\tau^\{\-1\}\\sigmabe the relative permutation, and extend it with sentinelsπ0=0\\pi\_\{0\}=0andπn\+1=n\+1\\pi\_\{n\+1\}=n\+1\. ThendB​\(σ,τ\)=\#​\{i∈\{0,…,n\}:\|πi\+1−πi\|\>1\}d\_\{B\}\(\\sigma,\\tau\)=\\\#\\\{i\\in\\\{0,\\dots,n\\\}:\|\\pi\_\{i\+1\}\-\\pi\_\{i\}\|\>1\\\}\.

## 3\.Related Work

Permutation puzzles and Cayley graphs\.The connection between permutation puzzles and Cayley graphs is classical: each puzzle state is a vertex, and each legal move is an edge labeled by a generator\. The generalized\(n2−1\)\(n^\{2\}\-1\)\-puzzle was shown to be NP\-hard by Ratner and Warmuth\[[9](https://arxiv.org/html/2607.13219#bib.bib9)\]\. For the TopSpin puzzle specifically, the group\-theoretic structure—in particular, which permutations are reachable for givennnandkk—has been analyzed in\[[7](https://arxiv.org/html/2607.13219#bib.bib7),[10](https://arxiv.org/html/2607.13219#bib.bib10)\]\. The standard TopSpin\(20,4\)\(20,4\)puzzle with20\!20\!states is well\-known for generating the full symmetric groupS20S\_\{20\}whenk=4k=4\.

Optimal solving and pattern databases\.Bortoluzzi\[[1](https://arxiv.org/html/2607.13219#bib.bib1)\]developed a domain\-specific solver for TopSpin using pattern database heuristics with IDA\*\. By precomputing distances in abstracted subproblems, pattern databases provide admissible heuristics that dramatically prune the search tree\. However, the approach is limited by the exponential growth of the database: even moderate pattern sizes \(3–6 tokens\) require substantial memory and precomputation time, and scaling beyondn=9n=9proves challenging\.

Diameter and distance problems\.The diameter of the TopSpin Cayley graphΓ​\(Sn,\{L,R,Xk\}\)\\Gamma\(S\_\{n\},\\\{L,R,X\_\{k\}\\\}\)is conjectured to beΘ​\(n2\)\\Theta\(n^\{2\}\)\. Chervov and Soibelman\[[4](https://arxiv.org/html/2607.13219#bib.bib4)\]study the closely related LRX Cayley graph and conjecture its diameter to ben​\(n−1\)/2n\(n\-1\)/2\. In a subsequent work, Chervov et al\.\[[5](https://arxiv.org/html/2607.13219#bib.bib5)\]propose a holographic duality framework for Cayley graphs ofSnS\_\{n\}, mapping vertices to lattice paths inside planar polygons, with word metrics corresponding to areas under the paths; this connects diameter computations to Ehrhart quasi\-polynomials and provides a geometric perspective on permutation distances\.

Search algorithms for large state spaces\.Bidirectional BFS is the standard technique for reducing the search frontier fromO​\(bd\)O\(b^\{d\}\)toO​\(bd/2\)O\(b^\{d/2\}\), wherebbis the branching factor andddthe solution depth\. For very large state spaces, randomized methods become attractive: random walks on Cayley graphs are studied extensively in the context of mixing times\[[6](https://arxiv.org/html/2607.13219#bib.bib6)\]and the Babai conjecture on diameters of Cayley graphs of simple groups\.

The present approach\.The cycle intersection strategy of the present paper differs from the above methods in several respects\. Unlike BFS or IDA\*, it does not explore the graph level by level and does not guarantee shortest paths\. Unlike pattern databases, it requires no precomputation and no memory\-intensive lookup tables\. Unlike random walk methods, it does not rely on mixing properties but instead exploits the algebraic structure of cycles—the fact that a composed permutationφw\\varphi\_\{w\}has finite order and its iterates systematically cover a large region of the state space\. The closest relative is the meet\-in\-the\-middle paradigm, but here the “meeting depth” is not fixed a priori; instead, it is discovered dynamically through cycle intersections and iterated bridge selection\.

## 4\.The Iterative Cycle Intersection Algorithm

We now describe the main algorithm implemented incayleyR\. The input is a pair of statesσs\\sigma\_\{s\}\(start\) andσf\\sigma\_\{f\}\(final\) in the Cayley graphΓ​\(G,\{L,R,Xk\}\)\\Gamma\(G,\\\{L,R,X\_\{k\}\\\}\), and the output is a sequence of generators transformingσs\\sigma\_\{s\}intoσf\\sigma\_\{f\}\.

### 4\.1\.Overview

The algorithm maintains two*state stores*𝒮\\mathcal\{S\}andℱ\\mathcal\{F\}, expanding fromσs\\sigma\_\{s\}andσf\\sigma\_\{f\}respectively\. Each iteration \(called a*cycle expansion round*\) proceeds in four phases:

1. \(1\)Random combination generation\.A batch of random operation sequencesw\(1\),…,w\(N\)w^\{\(1\)\},\\dots,w^\{\(N\)\}of a prescribed lengthℓ\\ellis generated over the alphabet\{L,R,Xk\}\\\{L,R,X\_\{k\}\\\}\. Each sequence is evaluated on the current seed state to determine its cycle length \(Definition[3](https://arxiv.org/html/2607.13219#Thmtheorem3)\)\. The top sequences—ranked by cycle length, number of unique states, or another criterion—are retained\.
2. \(2\)Cycle expansion\.For each retained sequencew\(j\)w^\{\(j\)\}, the full cycle is unrolled: all intermediate states are computed and inserted into the corresponding state store \(𝒮\\mathcal\{S\}orℱ\\mathcal\{F\}\) together with metadata \(step index, combination index, cycle number, operation label\)\.
3. \(3\)Intersection check\.The algorithm queries whether𝒮∩ℱ≠∅\\mathcal\{S\}\\cap\\mathcal\{F\}\\neq\\varnothingusing hash\-indexed lookup\. If an intersection stateσ∗\\sigma^\{\*\}is found, the path is reconstructed \(Section[4\.2](https://arxiv.org/html/2607.13219#S4.SS2)\) and the algorithm terminates\.
4. \(4\)Bridge selection\.If no intersection is found, a bridge state is selected from each side\. Let𝒰𝒮=unique​\(𝒮\)\\mathcal\{U\}\_\{\\mathcal\{S\}\}=\\mathrm\{unique\}\(\\mathcal\{S\}\)and𝒰ℱ=unique​\(ℱ\)\\mathcal\{U\}\_\{\\mathcal\{F\}\}=\\mathrm\{unique\}\(\\mathcal\{F\}\)\. The key idea is that each front searches for states close to the*opposite*endpoint: states in𝒰𝒮\\mathcal\{U\}\_\{\\mathcal\{S\}\}\(expanded from the start\) are ranked by their distance toσf\\sigma\_\{f\}, and states in𝒰ℱ\\mathcal\{U\}\_\{\\mathcal\{F\}\}\(expanded from the final\) are ranked by their distance toσs\\sigma\_\{s\}\. This symmetric criterion drives both fronts toward each other\. From the 10 closest states on each side, one is chosen uniformly at random\. These two states become the seed states for the next round\.

The procedure repeats until an intersection is found or a maximum iteration count is reached\.

Algorithm 1Iterative Cycle Intersection \(ICI\)0:States

σs,σf∈G\\sigma\_\{s\},\\sigma\_\{f\}\\in G; turnstile width

kk; moves

\{L,R,Xk\}\\\{L,R,X\_\{k\}\\\}; combo length

ℓ\\ell; sample count

NN; top count

NtopN\_\{\\mathrm\{top\}\}; max iterations

TT; distance function

dd\.

0:Operation sequence

PPsuch that

P​\(σs\)=σfP\(\\sigma\_\{s\}\)=\\sigma\_\{f\}, or FAIL\.

1:

𝒮←CreateStore​\(\)\\mathcal\{S\}\\leftarrow\\texttt\{CreateStore\}\(\);

ℱ←CreateStore​\(\)\\mathcal\{F\}\\leftarrow\\texttt\{CreateStore\}\(\)
2:

βs←σs\\beta\_\{s\}\\leftarrow\\sigma\_\{s\};

βf←σf\\beta\_\{f\}\\leftarrow\\sigma\_\{f\}\{current seed states\}

3:

Bs←\[\(σs,0\)\]B\_\{s\}\\leftarrow\[\(\\sigma\_\{s\},0\)\];

Bf←\[\(σf,0\)\]B\_\{f\}\\leftarrow\[\(\\sigma\_\{f\},0\)\]\{bridge state histories\}

4:for

t=1t=1to

TTdo

5:\{— Forward expansion —\}

6:

Ws←SampleCombos​\(ℓ,N\)W\_\{s\}\\leftarrow\\texttt\{SampleCombos\}\(\\ell,N\)
7:

Ws∗←RankAndFilter​\(Ws,βs,k,Ntop\)W\_\{s\}^\{\*\}\\leftarrow\\texttt\{RankAndFilter\}\(W\_\{s\},\\beta\_\{s\},k,N\_\{\\mathrm\{top\}\}\)
8:

ExpandCycles​\(𝒮,Ws∗,βs,k,t\)\\texttt\{ExpandCycles\}\(\\mathcal\{S\},W\_\{s\}^\{\*\},\\beta\_\{s\},k,t\)
9:

10:\{— Backward expansion —\}

11:

Wf←SampleCombos​\(ℓ,N\)W\_\{f\}\\leftarrow\\texttt\{SampleCombos\}\(\\ell,N\)
12:

Wf∗←RankAndFilter​\(Wf,βf,k,Ntop\)W\_\{f\}^\{\*\}\\leftarrow\\texttt\{RankAndFilter\}\(W\_\{f\},\\beta\_\{f\},k,N\_\{\\mathrm\{top\}\}\)
13:

ExpandCycles​\(ℱ,Wf∗,βf,k,t\)\\texttt\{ExpandCycles\}\(\\mathcal\{F\},W\_\{f\}^\{\*\},\\beta\_\{f\},k,t\)
14:

15:\{— Intersection check —\}

16:

I←𝒮∩ℱI\\leftarrow\\mathcal\{S\}\\cap\\mathcal\{F\}\{hash\-based,

O​\(min⁡\(\|𝒮\|,\|ℱ\|\)\)O\(\\min\(\|\\mathcal\{S\}\|,\|\\mathcal\{F\}\|\)\)\}

17:if

I≠∅I\\neq\\varnothingthen

18:Choose

σ∗∈I\\sigma^\{\*\}\\in I
19:

Ps←ReconstructPath​\(𝒮,Bs,σ∗\)P\_\{s\}\\leftarrow\\texttt\{ReconstructPath\}\(\\mathcal\{S\},B\_\{s\},\\sigma^\{\*\}\)
20:

Pf←ReconstructPath​\(ℱ,Bf,σ∗\)P\_\{f\}\\leftarrow\\texttt\{ReconstructPath\}\(\\mathcal\{F\},B\_\{f\},\\sigma^\{\*\}\)
21:return

Ps⋅Invert​\(Pf\)P\_\{s\}\\cdot\\texttt\{Invert\}\(P\_\{f\}\)
22:endif

23:

24:\{— Bridge selection —\}

25:

𝒰𝒮←Unique​\(𝒮\)\\mathcal\{U\}\_\{\\mathcal\{S\}\}\\leftarrow\\texttt\{Unique\}\(\\mathcal\{S\}\);

𝒰ℱ←Unique​\(ℱ\)\\mathcal\{U\}\_\{\\mathcal\{F\}\}\\leftarrow\\texttt\{Unique\}\(\\mathcal\{F\}\)
26:

Δs←\{\(τ,d​\(σf,τ\)\):τ∈𝒰𝒮\}\\Delta\_\{s\}\\leftarrow\\\{\(\\tau,d\(\\sigma\_\{f\},\\tau\)\):\\tau\\in\\mathcal\{U\}\_\{\\mathcal\{S\}\}\\\}; sort ascending

27:

Δf←\{\(τ,d​\(σs,τ\)\):τ∈𝒰ℱ\}\\Delta\_\{f\}\\leftarrow\\\{\(\\tau,d\(\\sigma\_\{s\},\\tau\)\):\\tau\\in\\mathcal\{U\}\_\{\\mathcal\{F\}\}\\\}; sort ascending

28:

βs←RandomFrom​\(Top10​\(Δs\)\)\\beta\_\{s\}\\leftarrow\\texttt\{RandomFrom\}\(\\texttt\{Top\}\_\{\\\!10\}\(\\Delta\_\{s\}\)\)
29:

βf←RandomFrom​\(Top10​\(Δf\)\)\\beta\_\{f\}\\leftarrow\\texttt\{RandomFrom\}\(\\texttt\{Top\}\_\{\\\!10\}\(\\Delta\_\{f\}\)\)
30:Append

\(βs,t\)\(\\beta\_\{s\},t\)to

BsB\_\{s\}; Append

\(βf,t\)\(\\beta\_\{f\},t\)to

BfB\_\{f\}
31:endfor

32:returnFAIL

### 4\.2\.Path reconstruction

When an intersection stateσ∗\\sigma^\{\*\}is found in cyclet∗t^\{\*\}, the full path fromσs\\sigma\_\{s\}toσf\\sigma\_\{f\}is assembled by chaining the cycle segments across all rounds\. Concretely, the bridge historyBs=\[\(βs\(0\),0\),\(βs\(1\),1\),…\]B\_\{s\}=\\bigl\[\(\\beta\_\{s\}^\{\(0\)\},0\),\(\\beta\_\{s\}^\{\(1\)\},1\),\\dots\\bigr\]records the seed state used in each round\. Each seedβs\(i\)\\beta\_\{s\}^\{\(i\)\}is itself a state that was reached in roundi−1i\-1, so its position inside the store𝒮\\mathcal\{S\}is known\. The reconstruction proceeds as follows:

1. \(1\)In roundt∗t^\{\*\}, locateσ∗\\sigma^\{\*\}in𝒮\\mathcal\{S\}: identify the combinationw\(j\)w^\{\(j\)\}and step index within that combination’s cycle\. Read off the operation labels fromβs\(t∗\)\\beta\_\{s\}^\{\(t^\{\*\}\)\}toσ∗\\sigma^\{\*\}\.
2. \(2\)Trace backward: in roundt∗−1t^\{\*\}\-1, locateβs\(t∗\)\\beta\_\{s\}^\{\(t^\{\*\}\)\}and read the operations fromβs\(t∗−1\)\\beta\_\{s\}^\{\(t^\{\*\}\-1\)\}toβs\(t∗\)\\beta\_\{s\}^\{\(t^\{\*\}\)\}\.
3. \(3\)Continue until round0, reachingσs\\sigma\_\{s\}\.
4. \(4\)Concatenate all operation segments in order to obtainPsP\_\{s\}\.
5. \(5\)Symmetrically, reconstructPfP\_\{f\}fromσf\\sigma\_\{f\}toσ∗\\sigma^\{\*\}throughℱ\\mathcal\{F\}\.
6. \(6\)The final path isPs⋅Invert​\(Pf\)P\_\{s\}\\cdot\\mathrm\{Invert\}\(P\_\{f\}\), whereInvert\\mathrm\{Invert\}reverses the sequence and swapsL↔RL\\leftrightarrow R\(sinceR=L−1R=L^\{\-1\}\), leavingXkX\_\{k\}unchanged \(sinceXk=Xk−1X\_\{k\}=X\_\{k\}^\{\-1\}\)\.

The reconstruction described above is implemented instore\_reconstruct\_path\(\), which traverses the bridge chain from the root to the intersection stateσ∗\\sigma^\{\*\}\. For each consecutive pair\(βs\(i\),βs\(i\+1\)\)\(\\beta\_\{s\}^\{\(i\)\},\\beta\_\{s\}^\{\(i\+1\)\}\)in the bridge history, the algorithm identifies the combinationw\(j\)w^\{\(j\)\}that containsβs\(i\+1\)\\beta\_\{s\}^\{\(i\+1\)\}as an intermediate state; all intermediate states of that combination are ordered by their step index, and the operations up to the step at whichβs\(i\+1\)\\beta\_\{s\}^\{\(i\+1\)\}appears are collected\. The resulting segments are concatenated to formPsP\_\{s\}\. For the backward front, the analogous pathPfP\_\{f\}is inverted viainvert\_path\(\): the sequence is reversed and each operation is replaced by its inverse \(L↔RL\\leftrightarrow R,Xk↦XkX\_\{k\}\\mapsto X\_\{k\}\)\.

## 5\.ThecayleyRFramework

ThecayleyRpackage\[[2](https://arxiv.org/html/2607.13219#bib.bib2)\]is implemented in R with performance\-critical components in C\+\+ viaRcpp\. It is available on CRAN at[https://CRAN\.R\-project\.org/package=cayleyR](https://cran.r-project.org/package=cayleyR)\. The package exposes approximately 70 functions organized into several layers: primitive permutation operations, cycle analysis, pathfinding strategies, state storage, distance computation, and GPU acceleration\. We describe each layer below\.

### 5\.1\.Primitive operations

The three generatorsLL,RR,XkX\_\{k\}\(equations \([1](https://arxiv.org/html/2607.13219#S2.E1)\)–\([3](https://arxiv.org/html/2607.13219#S2.E3)\)\) are implemented in C\+\+ asshift\_left,shift\_right, andreverse\_prefix\. Each function takes a permutation state \(integer vector of lengthnn\) and returns the transformed state\. Two variants are provided: a*simple*variant that performs only the permutation, and a*tracking*variant that additionally maintains cumulative operation counts\(nL,nR,nX\)\(n\_\{L\},n\_\{R\},n\_\{X\}\)used for celestial coordinate computation \(Section[5\.6](https://arxiv.org/html/2607.13219#S5.SS6)\)\.

The functionapply\_operationscomposes an arbitrary sequence of generators, accepting operations encoded as"1"/"L"\(left shift\),"2"/"R"\(right shift\), and"3"/"X"\(prefix reversal\)\.

###### Example 8\(Basic usage\)\.

The following R session illustrates the primitive operations for TopSpin\(20,4\)\(20,4\)\. An interactive demonstration is available as a Kaggle notebook\.111[https://www\.kaggle\.com/code/lbsbmsu/cayleyr\-demo\-topspin](https://www.kaggle.com/code/lbsbmsu/cayleyr-demo-topspin)

1library\(cayleyR\)

2n<\-20;k<\-4

3state<\-1:n

4

5

6shift\_left\(state\)

7

8

9shift\_right\(state\)

10

11

12reverse\_prefix\(state,k\)

13

14

15

16ops<\-c\("1","1","3","2"\)

17apply\_operations\(state,ops,k\)

18

19

20

21target<\-generate\_state\(n,k,n\_moves=100\)

22

23

24result<\-find\_path\_iterative\(state,target,k,

25combo\_length=25,n\_samples=400,

26n\_top=100,max\_iterations=150,

27sort\_by=c\("longest","most\_unique"\)\)

28result$path\_length

29

30

31

32final<\-apply\_operations\(state,result$path,k\)

33all\(final==target\)

34

### 5\.2\.Cycle analysis

Given a finite operation sequencew=\(w1,…,wm\)w=\(w\_\{1\},\\dots,w\_\{m\}\), the functionget\_reachable\_statesrepeatedly applieswwstarting from a given stateσ0\\sigma\_\{0\}until the state returns toσ0\\sigma\_\{0\}\(Definition[3](https://arxiv.org/html/2607.13219#Thmtheorem3)\)\. It records every intermediate state visited during each application, yielding up toc​mcmstates for a cycle of lengthcc\. A lightweight C\+\+ variant,get\_reachable\_states\_light, returns only the cycle length and unique state count without materializing intermediate states; this is used during the ranking phase of Algorithm[1](https://arxiv.org/html/2607.13219#alg1)to quickly evaluate thousands of candidate sequences\.

The functionfind\_best\_random\_combinationsgeneratesNNrandom operation sequences of lengthℓ\\ellover\{L,R,Xk\}\\\{L,R,X\_\{k\}\\\}, evaluates each via the lightweight cycle detector \(parallelized with OpenMP\), and returns the topNtopN\_\{\\mathrm\{top\}\}sequences ranked by a user\-specified criterion: longest cycle, shortest cycle, most unique states, or most repeated states\.

### 5\.3\.Pathfinding: three levels

The package provides three pathfinding strategies, each suited to a different regime of problem size\.

#### 5\.3\.1\.Exact BFS

The functionbidirectional\_bfsperforms classical bidirectional breadth\-first search, expanding from bothσs\\sigma\_\{s\}andσf\\sigma\_\{f\}level by level until the two frontiers meet\. This guarantees a shortest path in the Cayley graph but is limited to small instances \(n≲10n\\lesssim 10\) due to theO​\(n\!\)O\(n\!\)state space\.

#### 5\.3\.2\.Iterative Cycle Intersection

The functionfind\_path\_iterativeimplements Algorithm[1](https://arxiv.org/html/2607.13219#alg1)\. Its primary parameters directly correspond to the algorithm’s variables:

- •combo\_length\(ℓ\\ell\): length of random operation sequences generated per round\.
- •n\_samples\(NN\): number of random sequences generated per round\.
- •n\_top\(NtopN\_\{\\mathrm\{top\}\}\): number of top\-ranked sequences retained for full cycle expansion\.
- •max\_iterations\(TT\): maximum number of cycle expansion rounds\.
- •distance\_method: the heuristic used for bridge selection \("manhattan"or"breakpoint"\)\.
- •sort\_by: a vector of ranking criteria applied sequentially; the recommended valuec\("longest", "most\_unique"\)first selects sequences with the longest cycles, then re\-ranks by the number of unique states visited, maximizing both cycle coverage and state diversity \(see Table[1](https://arxiv.org/html/2607.13219#S6.T1)\)\.

Several additional parameters control fine\-grained search behavior:

- •potc∈\(0,1\]\\in\(0,1\]\(proportion of top combinations\): fraction of cycle states retained in the store\. A value of 1 corresponds to full cycle expansion; smaller values reduce memory usage by sampling a subset of intermediate states\.
- •ptr\(paths to reconstruct\): limits the number of intersections processed per round\. When the intersection check finds multiple shared states, a random sample of at mostptrcandidates is selected\. For each candidate, the full path is reconstructed and validated; the shortest valid path is chosen\. This prevents excessive reconstruction time when many intersections exist\.
- •opd\(one\-path\-detection\): when enabled, restricts the store queries to states belonging only to those combinations that contain the current bridge state\. This reduces the effective store size and eliminates noise from unrelated combinations during bridge selection, at the cost of discarding potentially useful states\.
- •reuse\_combos: when enabled, random operation sequences are generated once \(in the first round\) and reused in subsequent rounds, reducing generation overhead at the cost of lower diversity\.

The internal implementation uses the C\+\+StateStore\(Section[5\.5](https://arxiv.org/html/2607.13219#S5.SS5)\) for all state accumulation and lookup\. Bridge selection is refined through two mechanisms:

1. \(1\)*Middle\-state filtering\.*The functionstore\_filter\_middleexcludes the first and last states of each combination’s cycle \(by default, 5 from each end\)\. This prevents the bridge from snapping back to states near the current seed, which would cause the search to stagnate\.
2. \(2\)*Asymmetric greedy convergence\.*The bridge state on the start side is selected as the state closest to the*current final\-side seed*\(not toσf\\sigma\_\{f\}itself\)\. The bridge on the final side is then selected as the state closest to the*newly chosen start\-side bridge*\. This two\-step greedy procedure drives the two fronts toward each other rather than independently toward the original endpoints\.

#### 5\.3\.3\.Hub\-based transport network

The functionfind\_path\_bfsimplements a multi\-step strategy that constructs sparse*highway trees*from both endpoints, selects the closest hub pair, and delegates the remaining gap to the ICI algorithm\. We describe each step in detail\.

Step 1: Sparse BFS highway construction\.From each endpoint \(σs\\sigma\_\{s\}andσf\\sigma\_\{f\}\), the C\+\+ functionsparse\_bfsbuilds a tree of hub states up to a prescribed depth \(controlled bybfs\_levels, typically 200–500\)\. Unlike full BFS—which stores all3d3^\{d\}states at depthdd—sparse BFS retains only a bounded number of states per level, selected by two criteria:

- •*Exploitation*: the topbfs\_n\_hubsstates ranked by branching degree \(number of new children not yet seen\) are kept\. These high\-degree nodes maximize local coverage\.
- •*Exploration*: an additionalbfs\_n\_randomstates are chosen uniformly at random from the remaining candidates\. This prevents the tree from collapsing into a narrow corridor\.

The result is a compact edge table \(parent key, child key, operation, level\) encoding a tree rooted at the endpoint\. For typical parameters \(bfs\_n\_hubs=7\{\}=7,bfs\_n\_random=3\{\}=3,bfs\_levels=200\{\}=200\), each tree contains roughly 2000 edges representing states reachable within a few hundred moves via exact BFS paths\.

Step 2: Closest hub pair selection\.LetHsH\_\{s\}andHfH\_\{f\}denote the sets of unique states \(child keys\) in the start and final highway trees\. The algorithm computes pairwise distances between states inHsH\_\{s\}andHfH\_\{f\}using the chosen distance metric \(Manhattan or breakpoint\)\. If the sets are large, a random subsample of up to 500 states per side is used\. When a Vulkan GPU is available, the full distance matrix is computed viamanhattan\_distance\_matrix\_gpu; otherwise, a CPU double loop is used\.

The pair\(ηs,ηf\)\(\\eta\_\{s\},\\eta\_\{f\}\)with minimum distance is selected\. As a safeguard, the algorithm also compares this hub distance to the direct distanced​\(σs,σf\)d\(\\sigma\_\{s\},\\sigma\_\{f\}\)between the original endpoints\. If the direct distance is smaller—meaning the highways did not find a useful shortcut—the algorithm falls through to run ICI directly on\(σs,σf\)\(\\sigma\_\{s\},\\sigma\_\{f\}\)without using hubs\.

Step 3: Special case—matching hubs\.Ifηs=ηf\\eta\_\{s\}=\\eta\_\{f\}\(the two highway trees discovered a common state\), no ICI search is needed\. The path is assembled directly from the two BFS segments:σs→ηs\\sigma\_\{s\}\\to\\eta\_\{s\}from the start tree andηf→σf\\eta\_\{f\}\\to\\sigma\_\{f\}\(inverted\) from the final tree\.

Step 4: ICI between hubs\.If the hubs are distinct, the algorithm invokesfind\_path\_iterative\(Algorithm[1](https://arxiv.org/html/2607.13219#alg1)\) withηs\\eta\_\{s\}as start andηf\\eta\_\{f\}as final\. All additional parameters \(combination length, sample count, ranking criterion, etc\.\) are passed through\. Because the highway trees have already “absorbed” the easy portion of the distance, the effective gap between hubs is typically much smaller than the original distance, leading to faster convergence and shorter paths\.

Step 5: Path assembly and verification\.The full path is assembled as:

PBFS​\(σs→ηs\)⏟exact BFS from start to hub⋅PICI​\(ηs→ηf\)⏟ICI between hubs⋅Invert​\(PBFS​\(σf→ηf\)\)⏟inverted BFS from final to hub\.\\underbrace\{P\_\{\\mathrm\{BFS\}\}\(\\sigma\_\{s\}\\to\\eta\_\{s\}\)\}\_\{\\text\{exact BFS from start to hub\}\}\\;\\cdot\\;\\underbrace\{P\_\{\\mathrm\{ICI\}\}\(\\eta\_\{s\}\\to\\eta\_\{f\}\)\}\_\{\\text\{ICI between hubs\}\}\\;\\cdot\\;\\underbrace\{\\mathrm\{Invert\}\\bigl\(P\_\{\\mathrm\{BFS\}\}\(\\sigma\_\{f\}\\to\\eta\_\{f\}\)\\bigr\)\}\_\{\\text\{inverted BFS from final to hub\}\}\.The BFS segments are reconstructed byreconstruct\_bfs\_path, which traces each hub back to the root of its tree\. The inversion swapsL↔RL\\leftrightarrow Rand reverses the sequence\. Finally,validate\_and\_simplify\_pathverifies that applying the assembled path toσs\\sigma\_\{s\}yieldsσf\\sigma\_\{f\}, and applies algebraic simplifications\. If verification fails \(which can occur due to numerical issues in very long paths\), the algorithm reports failure\.

The function also maintains a*bridge chain*that records all intermediate states \(BFS origin, hub, ICI bridge states\) for diagnostic purposes and path visualization\.

###### Example 9\(Transport network pathfinding\)\.

The following session demonstratesfind\_path\_bfson TopSpin\(20,4\)\(20,4\)\.

1library\(cayleyR\)

2n<\-20;k<\-4

3start\_state<\-1:n

4final\_state<\-generate\_state\(n,k,n\_moves=200\)

5

6result<\-find\_path\_bfs\(start\_state,final\_state,k,

7bfs\_levels=200,bfs\_n\_hubs=7,

8bfs\_n\_random=3,

9combo\_length=25,n\_samples=400,

10n\_top=100,max\_iterations=150,

11sort\_by=c\("longest","most\_unique"\),

12potc=1,ptr=3,opd=TRUE\)

Typical output for this configuration:

Step1:BuildingBFShighways\(levels=200\)

BFSstart:1989edges

BFSfinal:1989edges

Step2:Findingclosesthubpair

Hubdistance:30Directdistance:68

Step3:Runningfind\_path\_iterativebetweenhubs

Found30intersectionsincycle1

Selectedpathoflength24operations

Step4:Assemblingfullpath

Fullpathlength:32

BFSstart\-\>hub:4\|ICIhub\-\>hub:24\|BFShub\-\>final:4

Verificationpassed

The sparse BFS trees reduce the effective distance from 68 to 30\. The ICI algorithm closes the remaining gap in a single cycle expansion round, producing a verified 32\-operation path:4\+24\+44\+24\+4\.

### 5\.4\.Path post\-processing

The paths produced by ICI are generally not shortest\. The package provides two post\-processing utilities:

- •short\_position: algebraic simplification that cancels inverse pairs \(L​R→εLR\\to\\varepsilon\), reduces consecutive shifts modulonn, and simplifies blocks between reversals\.
- •short\_path\_bfs: depth\-limited BFS hopping\. At each position along the path, a local BFS of depthddexplores nearby states; if any of them appears later in the original path, the algorithm jumps ahead, replacing the intervening segment with the shorter BFS route\.

### 5\.5\.C\+\+ state store

A central data structure is theStateStore, implemented entirely in C\+\+\. It provides compact, incremental, hash\-indexed storage of permutation states and is designed for the accumulate\-and\-intersect pattern of Algorithm[1](https://arxiv.org/html/2607.13219#alg1)\.

Each entry in the store consists of a permutation vector of fixed lengthnntogether with metadata: step index within the combination, combination index, cycle number, generator label, and celestial coordinates\. States are stored contiguously in a flat array; an open\-addressing hash table maps each unique permutation \(keyed by a combined hash of its elements\) to the list of array indices where it occurs\. This design achievesO​\(1\)O\(1\)amortized insertion and lookup\.

The key operations are:

- •store\_add\_from\_dfandstore\_analyze\_combos: bulk insertion from R data frames or direct C\+\+ cycle expansion\.
- •store\_find\_intersections: given two stores𝒮\\mathcal\{S\}andℱ\\mathcal\{F\}, returns the set of state keys present in both, inO​\(min⁡\(\|𝒮\|,\|ℱ\|\)\)O\(\\min\(\|\\mathcal\{S\}\|,\|\\mathcal\{F\}\|\)\)time\.
- •store\_reconstruct\_path: traces the chain of bridge states backward through successive cycles to assemble the full operation sequence\.
- •store\_filter\_middleandstore\_set\_opd: filtering operations that restrict queries to interior states of cycles or specific combination subsets, reducing noise in bridge selection\.

### 5\.6\.Celestial coordinates

Each state visited during cycle expansion is annotated with*celestial coordinates*, providing a geometric embedding of the search trajectory\. The construction is inspired by the celestial holography program of Pasterski\[[8](https://arxiv.org/html/2607.13219#bib.bib8)\], which establishes a duality between scattering amplitudes in four\-dimensional flat spacetime and correlators of a two\-dimensional conformal field theory on the celestial sphere\. We adapt this idea to the discrete setting of Cayley graphs: cumulative operation counts are mapped to points onS2S^\{2\}via stereographic projection\.

Let\(nL,nR,nX\)\(n\_\{L\},n\_\{R\},n\_\{X\}\)denote the cumulative counts of left shifts, right shifts, and reversals applied along the path from the seed state\. Define the complex coordinate

z=nL−nRnL\+nR\+nX\+1\+i​nXnL\+nR\+nX\+1\.z=\\frac\{n\_\{L\}\-n\_\{R\}\}\{n\_\{L\}\+n\_\{R\}\+n\_\{X\}\+1\}\+i\\,\\frac\{n\_\{X\}\}\{n\_\{L\}\+n\_\{R\}\+n\_\{X\}\+1\}\.The\+1\+1in the denominator ensureszzis well\-defined at the seed state itself, where\(nL,nR,nX\)=\(0,0,0\)\(n\_\{L\},n\_\{R\},n\_\{X\}\)=\(0,0,0\); in this casez=0z=0, corresponding to the origin of the stereographic plane\. Apply the inverse stereographic projection to obtain a point onS2S^\{2\}, yielding spherical coordinates\(θ,ϕ\)\(\\theta,\\phi\)and a conformal parameterω\\omega\. In the current implementation, these coordinates serve primarily as a*visualization tool*, mapping the search history onto the sphere to reveal geometric structure in the exploration pattern \(see Figure[2](https://arxiv.org/html/2607.13219#S7.F2)\)\. An angular distancedz​\(σ,τ\)d\_\{z\}\(\\sigma,\\tau\)between celestial positions is also available and can in principle be used for bridge selection; however, experiments to date have not shown this to be more effective than Manhattan or breakpoint distance on the permutation vectors themselves\. We regard celestial coordinates as an experimental feature whose full potential—particularly in connection with the holographic framework discussed in Section[7](https://arxiv.org/html/2607.13219#S7)—remains to be explored\.

### 5\.7\.GPU acceleration

When theggmlRpackage is installed and a Vulkan\-capable GPU is detected,cayleyRoffloads two computational bottlenecks to the GPU\.

#### 5\.7\.1\.Batch state transformation

Each generatorLL,RR,XkX\_\{k\}can be represented as ann×nn\\times npermutation matrix\. A composed operation sequencewwcorresponds to the matrix productMw=Mwm​⋯​Mw1M\_\{w\}=M\_\{w\_\{m\}\}\\cdots M\_\{w\_\{1\}\}\. Applyingwwto a batch ofBBstates is then a single matrix multiplicationMw⋅SM\_\{w\}\\cdot S, whereSSis then×Bn\\times Bstate matrix\. The functionapply\_operations\_batch\_gpuperforms this multiplication on the GPU, andstore\_analyze\_combos\_gpuintegrates it directly into the cycle expansion loop, bypassing the R layer entirely\.

#### 5\.7\.2\.Pairwise distance computation

Computing Manhattan distances between all pairs of states in two sets of sizesN1N\_\{1\}andN2N\_\{2\}is anO​\(N1​N2​n\)O\(N\_\{1\}N\_\{2\}n\)operation that dominates the bridge selection phase for large stores\. The functionmanhattan\_distance\_matrix\_gpuperforms this computation on the GPU in batches, avoiding host\-memory overflow for large state sets\.

## 6\.Computational Experiments

We present preliminary benchmarks illustrating the behavior of the ICI algorithm under different parameter settings\. All experiments were conducted usingcayleyRversion 0\.1\.0 on a Linux workstation with an AMD Ryzen 5 5600 \(6 cores, 12 threads\)\. Note: the current CRAN release is version 0\.2\.1; the core ICI algorithm and its parameters are unchanged between versions, so the results remain representative\.

### 6\.1\.Effect of the ranking criterion

Thesort\_byparameter controls which random operation sequences are retained after the sampling phase \(line 7 of Algorithm[1](https://arxiv.org/html/2607.13219#alg1)\)\. We compare six strategies across 12 random TopSpin instances withnnranging from 14 to 30,k=4k=4,n\_moves=100\{\}=100,max\_iterations=200\{\}=200, and a 30\-second timeout per strategy\. The start state is the identity and the target is a random permutation\.

Table 1\.Aggregatedsort\_bybenchmark: success rate and median time across 12 instances \(n=14n=14–3030,k=4k=4\)\.Table[1](https://arxiv.org/html/2607.13219#S6.T1)summarizes the results\. Several patterns emerge from the 12 runs\.

most\_uniqueachieves the highest success rate \(83%\), finding paths in 10 out of 12 instances\. However, the paths it produces are often very long \(up to 73 980 operations\), since it prioritizes state diversity over cycle structure\.

most\_repeatedis the most reliable fast strategy: 75% success rate with consistently short paths \(typically under 2000 operations\) and very low search times \(median under 1 second\)\. It selects sequences whose cycles revisit many states, which concentrates the search and increases intersection probability in dense regions of the graph\.

longestsucceeds in 58% of cases\. When it works, it often finds short paths quickly \(e\.g\., 4–6 operations in easy instances\), but it frequently times out on harder instances where long cycles fail to overlap\.

least\_repeatedis the weakest strategy \(25% success\), confirming that sequences with few repeated states produce sparse, non\-overlapping cycles\.

The combined strategies \(longest\+most\_uniqueandmost\_unique\+longest\) do not consistently outperform the single\-criterion strategies\. In some instances they find optimal short paths; in others they timeout\. Their behavior is sensitive to the interaction between the two ranking stages\.

A key observation is that no single strategy dominates across all instances\. The optimal choice depends on the specific permutation and puzzle size:most\_repeatedis a safe default for reliability, whilemost\_uniquemaximizes coverage at the cost of path length\. This variability motivates future work on adaptive strategy selection\.

### 6\.2\.Scalability with scramble distance

To assess how the algorithm scales with the difficulty of the target state, we fixn=14n=14,k=4k=4and vary the*scramble distance*n\_movesfrom 20 to 150 \(the number of random moves used to generate the target from the identity\)\. The algorithm isfind\_path\_bfswithbfs\_levels=200\{\}=200,bfs\_n\_hubs=7\{\}=7,bfs\_n\_random=3\{\}=3,sort\_by=\{\}=c\("longest", "most\_unique"\),combo\_length=25\{\}=25,n\_samples=400\{\}=400,n\_top=100\{\}=100,max\_iterations=150\{\}=150,potc=1\{\}=1,ptr=3\{\}=3,opd=\{\}=TRUE,distance\_method=\{\}="manhattan"\. Path shortening is applied viashort\_path\_bfs\. The column*Cycles*reports the number of ICI rounds executed in Step 4 \(hub\-to\-hub search\) offind\_path\_bfs\.

Table 2\.ICI performance on TopSpin\(14,4\)\(14,4\)as a function of scramble distance\.All 14 instances were solved successfully \(Table[2](https://arxiv.org/html/2607.13219#S6.T2)\)\. Several observations stand out\. First, the search time remains modest across all scramble distances: the mean search time is 1\.12 seconds, and even the hardest instance \(n\_moves=80\\texttt\{n\\\_moves\}=80, requiring 12 cycles\) is solved in 3\.5 seconds\. The total time including path shortening averages 2\.3 seconds\.

Second, the number of ICI cycles required is not monotonically related to the scramble distance\. Some instances atn\_moves=90\\texttt\{n\\\_moves\}=90or 100 are solved in 3 cycles, whilen\_moves=50\\texttt\{n\\\_moves\}=50requires 11\. This reflects the stochastic nature of the algorithm: the difficulty depends not just on the graph distance but on the particular cycle structure encountered during random sampling\.

Third, the path shortening step \(short\_path\_bfs\) provides substantial compression in many cases, reducing path length by up to 50% \(e\.g\., from 1342 to 643 atn\_moves=140\\texttt\{n\\\_moves\}=140\)\. However, the savings are inconsistent: atn\_moves=60\\texttt\{n\\\_moves\}=60the shortener achieves zero savings, while atn\_moves=50\\texttt\{n\\\_moves\}=50it removes 772 operations\. The shortening time is comparable to the search time, roughly doubling the total computation\.

Experiments with GPU acceleration and scalability fornnexceeding 20 will be reported in a future revision\.

### 6\.3\.Scalability with puzzle size

We also test how the algorithm scales with the puzzle sizenn, fixingk=4k=4andn\_moves=20\\texttt\{n\\\_moves\}=20while varyingnnfrom 10 to 16\. The algorithm and parameters are identical to Section[6\.2](https://arxiv.org/html/2607.13219#S6.SS2):find\_path\_bfswithbfs\_levels=200\{\}=200,combo\_length=25\{\}=25,n\_samples=400\{\}=400,n\_top=100\{\}=100,sort\_by=\{\}=c\("longest", "most\_unique"\)\.

Table 3\.ICI performance as a function of puzzle sizenn\(k=4k=4,n\_moves=20\\texttt\{n\\\_moves\}=20\)\.All seven instances were solved \(Table[3](https://arxiv.org/html/2607.13219#S6.T3)\)\. The search time remains under 0\.5 seconds for all sizes, with no visible growth trend fromn=10n=10ton=16n=16\. This is consistent with the design of the ICI algorithm: the per\-cycle cost is dominated by the number of states generated \(controlled byn\_samplesandcombo\_length\), not byn\!n\!\. The state space grows super\-exponentially withnn, but the algorithm only ever materializes a small fraction of it\.

The path lengths and cycle counts vary considerably across instances, again reflecting the stochastic nature of the method\. Notably, then=15n=15andn=16n=16instances are solved with paths of only 2 operations—the random target happened to be very close to the identity—whilen=12n=12requires 2 cycles and produces a long path \(1138\) that the shortener fails to compress\. These extremes illustrate that the algorithm’s behavior is primarily governed by the intrinsic difficulty of the particular instance rather than the nominal size of the state space\.

## 7\.Discussion and Future Directions

### 7\.1\.Toward holographic cycle intersection

A speculative but promising direction comes from the recently proposed holographic duality framework for Cayley graphs\[[5](https://arxiv.org/html/2607.13219#bib.bib5)\]\. In that work, vertices of the Cayley graphΓ​\(Sn,S\)\\Gamma\(S\_\{n\},S\)are mapped to lattice paths inside a planar polygon, with the key property that word metrics \(distances in the graph\) correspond to areas under the respective paths—a discrete realization of the “complexity==volume” principle from AdS/CFT holography\.

This geometric perspective suggests an alternative approach to cycle intersection detection\. A cycle in the Cayley graph—a closed walk generated by iterating an operation sequence—would map to a closed lattice path in the polygon\. Two cycles emanating from different seed states would map to two families of paths, and their intersection in the graph would correspond to a geometric intersection of paths in two dimensions\. Finding such intersections among piecewise\-linear curves inℝ2\\mathbb\{R\}^\{2\}is in principle far cheaper than hash\-based comparison in the fulln\!n\!\-element state space\.

ThecayleyRpackage already implements a coordinate embedding \(celestial coordinates, Section[5\.6](https://arxiv.org/html/2607.13219#S5.SS6)\) that maps operation counts to points on the unit sphere\. While this embedding is useful for visualization, it does not yet capture the algebraic structure needed for reliable intersection detection—in practice, states that are close on the sphere are not necessarily close in the Cayley graph\. A forthcoming visualization module will provide tools for exploring these geometric representations; sample outputs are shown in Figures[1](https://arxiv.org/html/2607.13219#S7.F1)–[2](https://arxiv.org/html/2607.13219#S7.F2)\.

![Refer to caption](https://arxiv.org/html/2607.13219v1/cycle_graph_3d.png)Figure 1\.Three\-dimensional layout of cycle states for TopSpin\(7,4\)\(7,4\)using celestial coordinates\(θ,ϕ,ω\)\(\\theta,\\phi,\\omega\)\. Light blue points represent all states visited during cycle analysis of multiple operation sequences; edges connect consecutive states within each cycle\. The red overlay highlights the longest cycle found\. Visualization produced by thecgvRpackage \(in development\)\.![Refer to caption](https://arxiv.org/html/2607.13219v1/celestial_3d.png)Figure 2\.Celestial coordinate embedding of cycle expansion states for TopSpin\(20,4\)\(20,4\)\. Each point is a permutation state mapped toS2S^\{2\}via stereographic projection of cumulative operation counts\(nL,nR,nX\)\(n\_\{L\},n\_\{R\},n\_\{X\}\); colors encode different operation sequences\. The red chain traces the recovered path through successive bridge states\. Spatial clustering reflects that similar operation sequences produce nearby celestial positions\.Significant challenges remain\. The holographic map in\[[5](https://arxiv.org/html/2607.13219#bib.bib5)\]is established for Cayley graphs generated by transpositions and specific generator sets; extending it to the TopSpin generators\{L,R,Xk\}\\\{L,R,X\_\{k\}\\\}requires further theoretical work\. The lift from polygon coordinates back to permutations must be computationally efficient, and it is not yet clear whether the map preserves enough structure for the TopSpin case to make geometric intersection detection practical\. We regard this as an open problem for future investigation\.

### 7\.2\.Further directions

The current implementation ofcayleyRis focused exclusively on the TopSpin\(n,k\)\(n,k\)puzzle: the generators\{L,R,Xk\}\\\{L,R,X\_\{k\}\\\}, the cycle analysis routines, and the path post\-processing are all tailored to the shift\-and\-reverse structure of TopSpin\. However, the underlying algorithmic ideas—iterative cycle intersection, hash\-indexed state stores, bridge selection by distance heuristics—are not inherently tied to this particular puzzle\. In principle, any permutation puzzle whose moves can be expressed as generators of a subgroup ofSnS\_\{n\}could be attacked with the same framework\. Natural candidates include pancake sorting \(prefix reversals of variable length\), burnt pancake \(signed prefix reversals\), and Hungarian Rings\.

Several concrete extensions are planned for future releases:

- •*Coordinate\-guided search\.*Using celestial or holographic coordinates to steer the cycle expansion toward the target, rather than relying solely on distance heuristics applied to permutation vectors\. This includes directional search: biasing the generation of operation sequences toward directions in coordinate space that point from the current state toward the target\.
- •*Multi\-point pathfinding\.*Accepting a list of waypoints and finding a path that visits them sequentially, reusing the accumulated state store between successive searches\. This extends the single\-pair ICI to a traveling\-salesman\-like regime where the search space built for one pair informs the next\.
- •*Combination library\.*Pre\-generating and caching libraries of high\-quality operation sequences \(ranked by cycle length or uniqueness\) that can be reused across multiple pathfinding queries, amortizing the sampling cost\.
- •*Visualization package\.*A companion R package \(cgvR, currently under development\) will provide interactive visualization of cycles, state stores, bridge trajectories, and coordinate embeddings on the celestial sphere\.
- •*Generalization beyond TopSpin\.*A modular generator interface allowing users to define custom move sets, with adapted path inversion and simplification routines for arbitrary generator–inverse pairs\.

Other directions under consideration include adaptive combination selection \(using reinforcement learning to bias toward sequences whose cycles are more likely to intersect\), and parallel search \(multiple workers expanding cycles from different bridge states with a shared state store\)\.

## 8\.Conclusion

We have presentedcayleyR, an R package that solves the TopSpin\(n,k\)\(n,k\)puzzle by detecting cycle intersections in Cayley graphs of the symmetric group\. The core contribution is the Iterative Cycle Intersection \(ICI\) algorithm, which generates random operation sequences from both the start and target states, expands their cycles, and searches for shared permutation states via hash\-indexed lookup\. When no intersection is found, distance\-guided bridge selection narrows the gap and the process repeats\.

The algorithm is complemented by a hub\-based transport network strategy that builds sparse BFS trees from both endpoints, reducing the effective search distance before invoking ICI\. The implementation combines R with a C\+\+ backend \(via Rcpp\) featuring an open\-addressing hash\-indexed state store, OpenMP\-parallelized combination evaluation, and optional Vulkan GPU acceleration for batch state transformations and pairwise distance computation\.

Computational experiments on TopSpin\(14,4\)\(14,4\)and TopSpin\(10−16,4\)\(10\{\-\}16,4\)demonstrate that the algorithm reliably finds paths in under a few seconds, with the ranking criterion for operation sequences having a significant impact on path quality\. The celestial coordinate embedding provides a visualization framework for the search geometry, and a companion visualization package \(cgvR\) is under development\.

The current implementation is specific to the TopSpin puzzle, but the underlying ideas—cycle intersection, bridge selection, hash\-indexed state stores—are applicable to any permutation puzzle expressible as a Cayley graph\. Future directions include coordinate\-guided search, multi\-point pathfinding, and integration with the holographic duality framework recently proposed for Cayley graphs ofSnS\_\{n\}\.

The package is open\-source and available on CRAN\[[2](https://arxiv.org/html/2607.13219#bib.bib2)\]\. A companion visualization package,cgvR, is also available on CRAN\[[3](https://arxiv.org/html/2607.13219#bib.bib3)\]\.

## References

- \[1\]Bortoluzzi, P\.P\. \(2012\)\. A pattern database approach for solving the TopSpin puzzle problem\.Bachelor thesis, University of Basel\.
- \[2\]Baramykov, Y\. \(2026\)\.cayleyR: Cayley Graph Analysis for Permutation Puzzles\. R package version 0\.2\.1, CRAN\.[https://CRAN\.R\-project\.org/package=cayleyR](https://cran.r-project.org/package=cayleyR)\(DOI: 10\.32614/CRAN\.package\.cayleyR\)\.
- \[3\]Baramykov, Y\. \(2026\)\.cgvR: Interactive 3D Visualization of Large Cayley Graphs via Vulkan\. R package version 0\.1\.2, CRAN\.[https://CRAN\.R\-project\.org/package=cgvR](https://cran.r-project.org/package=cgvR)\(DOI: 10\.32614/CRAN\.package\.cgvR\)\.
- \[4\]Chervov, A\., Soibelman, A\. \(2025\)\. CayleyPy RL: Pathfinding and reinforcement learning on Cayley graphs\.arXiv preprintarXiv:2502\.18663\.
- \[5\]Chervov, A\., Levkovich\-Maslyuk, F\., Smolensky, A\., et al\. \(2026\)\. CayleyPy\-4: AI\-Holography\. Towards analogs of holographic string dualities for AI tasks\.arXiv preprintarXiv:2603\.22195\.
- \[6\]Diaconis, P\. \(1988\)\.Group Representations in Probability and Statistics\. IMS Lecture Notes, Vol\. 11\.
- \[7\]Goldstein, R\. \(2015\)\. The group theory of TopSpin\.Senior thesis, Bard College\.
- \[8\]Pasterski, S\., Pate, M\., Raclariu, A\.\-M\. \(2021\)\. Celestial holography\.arXiv preprintarXiv:2111\.11392\.
- \[9\]Ratner, D\., Warmuth, M\.K\. \(1990\)\. The\(n2−1\)\(n^\{2\}\-1\)\-puzzle and related relocation problems\.J\. Symbolic Comput\., 10\(2\), 111–137\.
- \[10\]Senac, E\. \(2016\)\. The 15 puzzle and TopSpin\.Butler University Undergraduate Research Conference\.