🤖 AI

CayleyR: Solving the TopSpin puzzle via cycle intersection

This paper introduces cayleyR, an R package that solves the TopSpin(n,k) permutation puzzle by employing an iterative bidirectional search with cycle intersection detection in Cayley graphs, enhanced by C++ hashing and optional Vulkan GPU acceleration.

Original authors: Yuri Baramykov

Published 2026-07-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuri Baramykov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Puzzle of the Infinite Maze

Imagine you are standing in a massive, invisible maze where every turn you take changes the entire layout of the world around you. This isn't just a game of "left or right"; it's a game of permutations, a branch of mathematics called group theory that studies how things can be rearranged. Think of a deck of cards: if you shuffle them, you create a new order. If you shuffle them again, you create another. The "Cayley graph" is a map of every single possible order those cards could be in, connected by the moves you make to get from one order to another.

The specific puzzle this paper tackles is called TopSpin. Imagine a circular track with numbered tokens (like beads on a necklace) and a window that can flip a few of them over. You can spin the whole track or flip the tokens in the window. The goal is simple: get the beads from a messy jumble back to their perfect, numbered order. The problem is that as you add more beads, the number of possible arrangements explodes. For just 20 beads, there are more ways to arrange them than there are atoms in the universe. Traditional computer methods, which try to check every single path one by one, get stuck in this infinite maze almost immediately. This paper introduces a new way to navigate that maze, not by walking every path, but by throwing darts and hoping two of them land on the same spot.

The Paper: Throwing Darts in the Dark

In this paper, Yuri Baramykov introduces a new software tool called cayleyR and a clever strategy to solve the TopSpin puzzle, even when the puzzle is huge. Instead of trying to map the entire maze from start to finish, the author uses a method called Iterative Cycle Intersection (ICI).

Here is how it works, using a playful analogy: Imagine you and a friend are lost in a giant, circular forest (the Cayley graph). You start at opposite ends, and you both want to meet in the middle.

The Old Way: You both try to walk every single path, step by step, marking every tree you see. This takes forever because the forest is too big.
The cayleyR Way: Instead of walking carefully, you both grab a handful of "magic seeds" (random sequences of moves). You plant them and watch them grow into giant, looping vines (cycles). Because the forest is circular, these vines eventually loop back on themselves.
The Intersection: You keep throwing these seeds and growing vines. Eventually, one of your vines will cross paths with one of your friend's vines. When they touch, you've found a meeting point! You can then trace the path from your start, along your vine, to the meeting point, and then follow your friend's vine backward to their start.

The paper explains that this "vine-growing" strategy is much faster than walking every path. The software generates random sequences of moves, calculates the loops they create, and checks if any of those loops overlap with the loops generated from the other side. If they don't overlap right away, the software picks the two vines that are closest to each other (using a "distance guide") and starts growing new vines from those points. It repeats this process until the two sides meet.

What the Paper Actually Found

The author didn't just invent the idea; they built a working computer program to test it. Here is what the experiments showed:

It works on big puzzles: The software successfully solved TopSpin puzzles with up to 20 tokens (where the number of possible arrangements is 20 factorial, or about 2.4 quintillion). This is a size that would crash traditional computers.
It's fast: In tests with 14 tokens, the computer found a solution in an average of 1.12 seconds. Even the hardest puzzles in the test were solved in under 3.5 seconds.
Not all seeds are equal: The paper tested different ways to choose which "magic seeds" (random move sequences) to plant. They found that choosing sequences that visit the most unique spots (called "most unique") was the most likely to find a solution (solving 83% of the test cases), but the paths it found were sometimes very long. Choosing sequences that visited the same spots over and over ("most repeated") was the most reliable for finding short paths quickly.
It's not perfect: The paper is very clear that the paths found are not necessarily the shortest possible path. The algorithm finds a path, not always the best path. However, the software includes a "post-processing" step that tries to shorten the path afterward, sometimes cutting the number of moves in half.

What the Paper Rules Out (and What It Doesn't)

It is important to know what this paper says it doesn't do:

It is not a guarantee of the shortest path: The author explicitly states that the Iterative Cycle Intersection algorithm does not guarantee the shortest route. It finds a solution, but it might take a detour.
It is not a magic bullet for every puzzle yet: The current version of the software is specifically designed for the TopSpin puzzle. While the author suggests the idea could work for other puzzles (like pancake sorting), the paper only proves it works for TopSpin.
The "Holographic" idea is just a guess: The paper mentions a fancy new theory called "holographic duality" that might help visualize these puzzles as shapes on a sphere. However, the author admits this is speculative. They say it "remains to be explored" and that the current version of the software only uses this for pretty pictures, not for actually solving the puzzle.

The Bottom Line

This paper presents a new, playful, and highly effective way to solve a very hard math puzzle. By stopping the attempt to map the whole world and instead looking for where two random paths cross, the cayleyR software can solve TopSpin puzzles with 20 tokens in just a few seconds. It's a reminder that sometimes, in a giant maze, you don't need to know every turn; you just need to find a place where two wandering paths happen to meet. The software is free and available for anyone to try, though the author warns that while it finds solutions quickly, it doesn't always find the perfect one.

Technical Summary: CAYLEYR: SOLVING THE TOPSPIN PUZZLE VIA CYCLE INTERSECTION

1. Problem Statement
The paper addresses the computational challenge of solving the TopSpin $(n, k)$ puzzle, a permutation puzzle involving $n$ tokens on a circular track and a turnstile window of width $k$ . The goal is to transform a given initial permutation into a target permutation using two primary moves: a cyclic shift of the entire track (Left $L$ or Right $R$ ) and a reversal of the $k$ tokens within the turnstile ( $X_k$ ).

Algebraically, the state space corresponds to the Cayley graph $\Gamma(G, \{L, R, X_k\})$ , where $G$ is the symmetric group $S_n$ (for even $k$ ) or the alternating group $A_n$ (for odd $k$ ). Solving the puzzle equates to finding a path between two vertices in this graph. The authors note that for $n > 10$ , the state space ( $n!$ ) grows super-exponentially, rendering classical shortest-path algorithms like Breadth-First Search (BFS) intractable. Furthermore, the conjectured diameter of the graph is $\Theta(n^2)$ , compounding the difficulty.

2. Methodology: Iterative Cycle Intersection (ICI)
The paper proposes a fundamentally different strategy from level-by-level graph exploration: the Iterative Cycle Intersection (ICI) algorithm. Instead of expanding the search frontier uniformly, ICI generates random "cycles" from both the start and target states and searches for an intersection between these families of cycles.

The algorithm operates in iterative rounds, maintaining two state stores ( $S$ and $F$ ) expanding from the start ( $\sigma_s$ ) and final ( $\sigma_f$ ) states, respectively. Each round consists of four phases:

Random Combination Generation: A batch of random operation sequences (words) of length $\ell$ is generated.
Cycle Expansion: For each sequence, the algorithm computes the full cycle of states generated by repeatedly applying the composed permutation until it returns to the seed. All intermediate states are recorded in the respective store.
Intersection Check: The algorithm checks for shared states between $S$ and $F$ using hash-indexed lookups. If an intersection $\sigma^*$ is found, the path is reconstructed by tracing the cycle chains back to the origins.
Bridge Selection: If no intersection occurs, the algorithm selects "bridge states" to restart the expansion. States in $S$ are ranked by their distance to $\sigma_f$ , and states in $F$ are ranked by their distance to $\sigma_s$ . The top 10 closest states on each side are considered, and one is chosen randomly from each to serve as the new seed for the next round.

Path Reconstruction and Refinement:
When an intersection is found, the full path is assembled by chaining the segments across all rounds. The paper notes that the resulting path is not guaranteed to be the shortest. To address this, the package includes a post-processing step (short path bfs) that performs local, depth-limited BFS "hopping" to replace intervening segments with shorter routes.

Hybrid Strategy (Hub-Based Transport Network):
For larger instances, the paper describes a hybrid approach (find_path_bfs). This method first constructs sparse "highway trees" using limited-depth BFS from both endpoints to identify "hub" states. It then selects the closest pair of hubs and invokes the ICI algorithm to bridge the gap between them. This reduces the effective search distance before the stochastic cycle intersection phase begins.

3. Key Contributions
The paper outlines three principal contributions:

The ICI Algorithm: A novel pathfinding strategy for Cayley graphs of permutation groups that relies on cycle intersection and distance-guided bridge selection rather than exhaustive level expansion.
The cayleyR Package: An open-source R package (with a C++ backend via Rcpp) implementing the algorithm. Key features include:
- Hash-indexed state storage for $O(1)$ amortized insertion and lookup.
- Optional Vulkan GPU acceleration for batch state transformations and pairwise distance computations.
- "Celestial coordinates," a geometric embedding of operation counts onto a sphere for visualization and potential future heuristic use.
Scalability Demonstrations: Computational experiments showing the algorithm's ability to solve TopSpin instances with $n$ up to 20, a scale previously difficult for exact solvers.

4. Experimental Results
The authors present benchmarks on a Linux workstation (AMD Ryzen 5 5600) using cayleyR version 0.1.0/0.2.1:

Ranking Criteria: The choice of how to rank random operation sequences significantly impacts performance. The "most unique" criterion (prioritizing sequences that visit the most distinct states) achieved the highest success rate (83% on 12 instances, $n=14\text{--}30$ ) but often produced very long paths. Conversely, "most repeated" sequences offered high reliability (75% success) with consistently short paths and fast search times (median < 1s).
Scalability with Scramble Distance: On TopSpin(14, 4) with varying scramble distances ( $n_{moves}=20\text{--}150$ ), the algorithm solved all 14 instances. The mean search time was 1.12 seconds, with the total time (including path shortening) averaging 2.3 seconds. The number of ICI cycles required did not correlate monotonically with scramble distance, highlighting the stochastic nature of the method.
Scalability with Puzzle Size ( $n$ ): On instances with $n=10\text{--}16$ and fixed scramble distance, search times remained under 0.5 seconds. The authors attribute this to the fact that the algorithm only materializes a small fraction of the state space, making it less sensitive to the super-exponential growth of $n!$ compared to BFS.

5. Significance and Claims
The paper positions cayleyR as a practical tool for solving permutation puzzles that exceed the limits of classical exhaustive search. Its significance lies in:

Efficiency: It avoids the memory and time bottlenecks of pattern databases and BFS by using random cycle generation and hash-based intersection.
Scalability: It successfully handles instances up to $n=20$ , where the state space is $20!$ .
Modularity: While currently tailored to TopSpin, the authors claim the underlying framework (cycle intersection, bridge selection, hash-indexed stores) is applicable to other permutation puzzles (e.g., pancake sorting, Hungarian Rings) provided they can be modeled as Cayley graphs.

The authors remain modest regarding the optimality of the solutions, acknowledging that ICI does not guarantee shortest paths and that the "celestial coordinate" embedding is currently an experimental visualization tool rather than a proven heuristic for distance estimation. Future work is proposed to explore holographic duality frameworks for cycle intersection and to generalize the generator interface for broader puzzle classes.

The Puzzle of the Infinite Maze

The Paper: Throwing Darts in the Dark

What the Paper Actually Found

What the Paper Rules Out (and What It Doesn't)

The Bottom Line

More like this