Cayley graph search with Claude Code: what puzzle competitions look like in 2026 – Andrey Lukyanenko
Skip to main content
Cayley graph search with Claude Code: what puzzle competitions look like in 2026
08 July 2026
Cayley graph search with Claude Code: what puzzle competitions look like in 2026
Over the last couple of months, I worked on two Kaggle competitions in the CayleyPy series: IHES Picture Cube and Megaminx. Both are combinatorial puzzle solvers, and they can be reformulated as a search in an enormous implicit Cayley graph: each puzzle state is a vertex, each possible move is an edge, and solving means finding a short path back to the identity. This is a long term-activity: we have been researching these puzzles for a couple of years and have published several papers. This year we took another step toward solving them.
I remember working on this in 2024. At that time, all code was written by hand, and I spent a lot of time debugging it and digging into documentation. But much has changed in these two years: nowadays, agentic workflows are a significant part of my workflow, and I can delegate much of the implementation work to an LLM, focusing on decisions rather than specifics (even though I still have to review them).
I used Opus inside Claude Code as the implementation agent for both competitions. Claude wrote essentially all of the training scripts, beam-search variants, TPU ports, submission automation, and post-processing tools. I still reviewed the code, checked outputs, and made the experiment-level decisions. I focused on guiding it and preventing it from going too far down the wrong path (which it did quite often): I told it which ideas to try, which areas to research, when to stop iterating on a dead-end model, when to pivot, etc.
So this post is about two things. One is about working with Cayley graphs: how to combine learned distance heuristics, wide beam search, symmetry, and path post-processing to solve puzzle graphs far too large to search with DFS/BFS. The second one is about agentic workflow: what it actually looks like to run a research loop when an agent handles implementation and the human role shifts toward experimental design, plateau detection, and search strategy.
I share the scores reached by different methods as a proxy of progress. The leaderboard shows a single number (total moves over a fixed set of scrambles), but it is the logic behind the solutions that matters. Score improvement indicates we were able to find shorter paths, so higher places on the leaderboard reflect a better understanding of the search problem.
What’s a Cayley graph, and why would you solve one?
Let’s start with an explanation of what a Cayley graph is and how we can work with it.
We have a puzzle (like a Rubik’s cube). Possible moves (generators) are a small set of operations (like turning a face of the cube). The puzzle has a solved state, and we can scramble it by applying a sequence of moves. The goal is to find a sequence of moves that returns the puzzle to the solved state.
In a Cayley graph, we have one vertex per element (every reachable configuration of the puzzle), and an edge between two vertices whenever a single generator takes one to the other.. The solved state is the identity vertex; a scramble is some other vertex. Solving the puzzle is finding a path from the scramble back to the identity, and solving it well (the score that we care about) is finding a short one. The shortest possible path is the scramble’s true distance-to-solved; the largest such distance over all scrambles is the graph’s diameter, known to cubers as “God’s number”.
By Cayley’s theorem, every finite group is a group of permutations, so permutation puzzles are a concrete handle on finite group theory in general.
The significance of Cayley graphs
A Cayley graph is one of the standard ways of representing a group as a geometric object: vertices are elements, edges are generators, and the graph metric becomes a distance measure in the group. This is why these competitions combine discrete optimization with geometric group theory. The basic questions are genuinely hard — nobody proved the 3×3×3 cube’s God’s number is 20 until 2010, and the value for megaminx is unknown.
Why a brute search can’t solve it
These graphs are far too big to write down. The 3×3×3 cube has about 4.3 × 10^19 states; the megaminx has roughly 10^68, astronomically more. In practice, you don’t even try to store the graph — you keep one state and generate its neighbors on the fly. The graph is defined implicitly, by its generators.
Breadth-first from solved is fine for a few moves — on megaminx. the numbers of states are 1, 24, 408, 6208, 90144, 1.28M, then ~18M states at depth six — but depth seven is ~250M, and a real scramble is dozens of moves deep.
So you can’t compute the true distance-to-solved; you estimate it with a learned heuristic and search against it. The whole problem boils down to two questions: how good is...