CayleyPy Applies Neural Networks to Rubik's Cubes Where God's Number Is Unknown

The 3×3×3 Rubik's Cube has about 4.3×10^19 valid states, and since 2010 it has been known that any of them can be solved in at most 20 moves in the HTM metric. Tomas Rokicki and colleagues obtained this result by exhaustively analyzing the state space. For the 4×4×4 and 5×5×5 cubes, big cubes and the megaminx, the exact diameter of the Cayley graph is still unknown. The CayleyPy project approaches these puzzles from a different direction: neural-network search rather than exhaustive enumeration. One of the team's members published a write-up of the pipeline and the competition results on Habr.

The puzzle as a graph

The formalization is simple. The vertices of a Cayley graph are the puzzle's valid states, and the edges are the valid moves. Solving the puzzle in the minimum number of moves becomes a shortest-path problem from the current vertex to the solved state. The diameter of the graph, that is, the maximum of the shortest distances over all pairs of vertices, is the "God's number."

For 3×3×3 this calculation was feasible, although it required substantial computing resources and the use of symmetries to shrink the state space. As the puzzle grows, the picture changes. The 4×4×4 has on the order of 7.4×10^45 states, and the 5×5×5 about 2.8×10^74. A full traversal of the graph is impossible here. What remains are heuristics, upper and lower bounds, and the search for suboptimal solutions, which gradually narrow the gap to the unknown optimum.

What CayleyPy does

CayleyPy is an open-source library around which a series of Kaggle competitions is built. The task in them is to find optimal and suboptimal paths in Cayley graphs with a huge number of vertices. Participants submit solutions, and the platform verifies them and ranks them by the length of the paths found. For researchers, it is a free way to test ideas on a shared benchmark; for the organizers, it is a way to collect many different approaches to a single mathematical problem.

According to the announcement, the author covers three things in the article:

• the architecture of the CayleyPy neural-network pipeline;
• the results of competitions that have already ended;
• the terms of the current contests for big cubes, in which he takes part as a team member.

The available excerpt contains no figures on the lengths of the paths found or on the teams' placings, so judging how far the neural-network approach outperforms classical search will have to wait for the full text. The original headline claims exactly that: that the neural network beats classical methods. Which metrics and which baseline algorithms were used for the comparison cannot be determined from the announcement.

Why the approach matters beyond cubes

The general scheme is well known: a neural network learns to estimate the distance to the goal, and a search algorithm uses that estimate to avoid expanding unnecessary branches. Earlier work on solving the Rubik's Cube with reinforcement learning is built the same way. The value is that a Cayley graph is a clean mathematical laboratory. It has exact answers for small cases, scalable complexity and an unambiguous quality metric. If a method works on 3×3×3, it can be tested on 4×4×4 and beyond, showing where it breaks down.

Cayley graphs describe permutation groups, so diameter estimates and the search for short paths are of interest in combinatorics and group theory. Comparable structures appear in routing problems and network topologies, although it is too early to draw practical conclusions from a single publication.

What a practicing engineer can do with this

If you work with search and heuristics, the open CayleyPy repository on GitHub and the Kaggle contests offer a ready-made testbed for your own ideas on a problem where the answer can be measured in number of moves. A sensible place to start is with small puzzles where the diameter is known, checking the neural distance estimate against the exact value. Then move on to big cubes, where the competition is already over the lengths of the solutions found.

Readers should keep one caveat in mind: this is a review by a project participant, not an independent study. Any claims of superiority over classical search should be checked against the specific results tables and against which solvers were used for comparison.