The Shape of Distance: A Geometric Derivation of the Probability Distribution of Rubik’s Cube Solution Lengths

How known cube counts, optimal-search theory, and graph geometry combine to explain why the distribution rises, concentrates, and collapses.

To solve the puzzle, you must twist the cubes so that eventually each side returns to its original color. The challenge is the astounding number of potential variations — more than 43 quintillion of them.

Source: Getty Images

A Rubik’s Cube position, at first glance, may appear to be a disorderly physical object. Some states seem close to solved, some look hopelessly scrambled, and others are deceptively difficult despite showing clear patterns.

Mathematically, however, the cube is not unstructured at all. It is a finite space of configurations, and each legal turn can move it from one configuration to another on a graph.

The probability that a random position requires exactly x moves to solve is highly ordered, a question of graph distance rather than difficulty.

For the probability distribution, we may center the graph at the solved state and ask how the entire space of legal cube positions is arranged around it. In this sense, each value of x defines a distance shell, which represents the set of all configurations whose shortest solution requires exactly x face turns. These distances arise from the geometry of a *finite Cayley graph* with a fixed solved state, enormous branching near the center, many collisions between paths, and a hard outer boundary—at 20 moves for a full 3×3×3 cube. The distribution therefore rises as the shells grow; it concentrates where most legal positions lie and then collapses because no position is farther than hard outer boundary.

The above simulation shows an exact distance-shell decomposition of a Rubik’s-cube subgraph. Instead of drawing the full 3×3×3 cube graph, which is far too large to be presented directly, it follows the corner-permutation projection generated by the face turns U, R, and F, including inverses and half-turns. The solved state sits at the center, and each shell Sₓ contains all states whose shortest path from the solved has length x. The shell counts grow rapidly at first, peak when most reachable configurations lie at intermediate graph distance, and then collapse at the finite boundary. This subgraph visualizes the basic mechanism that also shapes the full 3×3×3 cube distribution.

Probability mass is determined by the number of states in each distance shell, not by how scrambled a position appears to the eye.

In what follows, the aim is not to claim a new computation of Rubik’s Cube shell counts, a new probability table, or a new proof of God’s number. The main numerical and algorithmic ingredients are already known: the Cayley-graph formulation of the cube group, the exact early shell counts, Kociemba’s probability distribution, Cube20’s outer-shell estimates, Korf’s branching-factor analysis, and the proof by Rokicki, Kociemba, Davidson, and Dethridge that the face-turn diameter is 20.

This article instead assembles these ingredients into a mathematically unified probability-geometric argument. We will see that optimal solution length becomes a random variable on a finite Cayley graph; its probabilities arise from distance shells around the solved state; the early shell counts reveal an almost exponential regime; the logarithmic slope recovers an effective branching factor close to Korf’s; and the later deviation from that regime reflects path collisions and the hard boundary at 20.

This contribution is not a new computation and numerics of the shell counts but a unified derivation and interpretation of the distribution’s shape from the geometry of the cube graph.

Rubik Ernő. Photo courtesy of Rózsavölgyi Gyöngyi (source CC)

The Rubik’s Cube as a group

Rokicki, Kociemba, Davidson, and Dethridge describe the cube as having roughly 4.3×1⁰¹⁹ positions, which they partition into about two billion cosets of a specially chosen subgroup in their proof that the cube’s diameter is 20. ⇱ ⇱

In mathematical terms, let G be the Rubik’s Cube group, the set of all reachable cube configurations. The solved cube is the identity element, e∈G and for the standard 3×3×3 cube, |G|=43,252,003,274,489,856,000.

This is the number of physically reachable positions after the constraints on corner twists, edge flips, and permutation parity have been considered.

The next step is to define a move metric. In the half-turn metric, also called the face-turn metric, every twist of one face counts as one move, whether it is a quarter turn or a half turn. Thus U, U´, U² each count as one move. The corresponding move set is:

so that |S|=18. With this choice, the move graph of the cube is the Cayley graph 𝚪=Cay(G,S). Its vertices are cube states. Two vertices g,h∈G are connected when one legal face turn takes one state to the other, h=sg for some s∈S, after choosing a left-action convention. Thus, solving the cube becomes a graph-distance problem.

The random variable: Optimal distance from solved

For each cube state g∈G, define D(g)=d(g,e), where d(g,e) is the shortest path length from g to the solved state e in the Cayley graph. Equivalently:

The function D:G→{0,1,…,20} assigns to every cube position its optimal solution length in the chosen metric.

The upper endpoint 20 is not heuristic. It is the so-called *God’s number in the half-turn metric. Rokicki *and colleagues ⇱ ⇱ proved computationally that

every position can be solved in “20 moves or less,” where a move is any twist of any face.

The probability distribution we seek is the distribution of the random variable D, under the assumption that the starting state is chosen uniformly from all reachable cube positions. Thus, for every x∈{0,1,…,20}, we have:

Define the distance shell 𝒮ₓ={g∈G:d(g,e)=x}. Then Nₓ=|𝒮ₓ| is the number of positions at distance x from solved, and therefore:

This abstract formula contains the entire distribution. The real difficulty, however, is to determine the shell sizes Nₓ.

Note: The uniformity assumption matters, and a uniformly random reachable cube position is not necessarily the same as a cube produced by a short random scramble. In this article, we consider the the uniform distribution on G.

Balls, shells, and why this is not Gaussian

The distance ball of radius x is Bₓ={g∈G:d(g,e)≤x}. It contains all cube positions that can be solved in at most x moves. The first shell consists only of the solved state, 𝒮₀={e} so N₀=1.

For x≥1, the shell at exact distance x is the new layer added when the ball grows from radius [x–1] to radius x:

Therefore, for x≥1:

and the probability mass at distance x is:

This formula also reveals why the distribution is a graph-shell distribution rather than a Gaussian. A Gaussian usually arises when a quantity behaves like the sum of many weakly dependent increments. The distance D(g), however, is not such a sum. It is a shortest-path distance in a finite Cayley graph, where the relevant object is not accumulated error but the number of states located in each successive shell.

For small x, the shells grow rapidly because each new layer opens many new positions. If the graph behaved like a tree, one would expect approximate exponential growth:

where 𝝀 is an effective branching factor.

But the Rubik’s Cube graph is not a tree. Korf’s analysis shows why the naive branching factor 18 is immediately reduced. ⇱ Consecutive twists of the same face create redundant descriptions, and commutations of opposite faces create further duplicate move sequences. After these reductions, Korf obtains an asymptotic branching factor of about 13.34847 for the reduced search tree. He also emphasizes that even this reduced tree does not coincide with the cube graph itself, because different move sequences can still reach the same cube state.

This early branching explains the rapid rise, but the same finite geometry prevents the rise from continuing indefinitely. As the balls Bₓ occupy more of the group, new paths increasingly collide with states that have already been reached. The shells stop behaving like expanding layers of a tree and begin to feel the finiteness of the cube group itself. For the full cube, the distribution therefore bends away from exponential growth, concentrates near distances 17 and 18, and then collapses at the hard boundary 20. So the distribution is not symmetric. It is pushed toward the outer part of the graph and cut off by a finite right boundary.

Known shell counts

The exact known values for the half-turn metric begin as follows:

OEIS A080601 ⇱ defines the sequence as the number of Rubik’s Cube positions at distance n from the solved state in the half-turn metric, beginning 1,18,243,3240,… **Kociemba’s probability table gives the same exact early shell counts and states that the theoretical distribution of God’s Algorithm is known only for maneuver lengths less than 16**. ⇱

For larger distances, the available values should be read as estimates rather than exact shell counts:

Kociemba ⇱ gives simulation estimates for the outer probability mass, and Cube20-related discussions commonly cite about 490 million positions at distance 20, while noting that the exact number of distance-20 positions remains unknown. This already reveals the essential shape, where the mass is overwhelmingly concentrated in the last few shells, especially at distance 18.

From shell counts to probabilities

Once the shell counts Nₓ are known or estimated, the probability distribution follows immediately by normalization:

The first probabilities are extraordinarily small because the inner shells contain so few states compared to the size of the full cube group. For the solved cube itself:

since there is only one solved position. Likewise:

because exactly 18 positions lie one face turn away from solved.

Kociemba gives the exact probabilities for the known early shells and then provides simulation estimates for the outer region, where exact theoretical distribution is not presently known. ⇱ His estimates are:

with p₂₀>0 but probably below 1/10¹¹.

The shape is unmistakable. A uniformly random cube is almost never close to solved.

Most positions lie deep in the outer shells of the Cayley graph, concentrated near distances 17 and 18, while the final shell at distance 20 is extraordinarily thin despite representing the maximal possible distance from solved.

The existence of distance-20 states does not mean that a random cube is usually extremely difficult. In fact, the opposite is true. Although the cube contains positions that provably require the maximal 20 face turns, those states occupy only a tiny outer fringe of the full graph.

This creates a geometric paradox. Distance-20 states are extraordinarily far from solved, yet statistically they stay almost invisible. Even if their number reaches hundreds of millions, the full cube group contains about 4.3×10¹⁹ reachable positions, so the corresponding probability remains astronomically small: p₂₀∼1/10¹¹.

Exponential shell growth and the logarithmic plot

The probability table gives the distribution numerically, but it still contains a second layer of information. Since pₓ=Nₓ/|G|, normalization changes the scale but not the shape. Any exponential pattern in the shell counts therefore remains visible in the probabilities.

The known shell counts reveal a striking regularity in the early part of the distribution: they grow at an almost exponential rate. This is what one would expect if the Cayley graph initially behaved approximately like an expanding tree, where each newly reached state opens many further states. In such a regime, the shell counts satisfy an approximate law of the form:

where 𝝀 is an effective branching factor. Since pₓ=Nₓ/|G| the probabilities themselves satisfy

Taking logarithms transforms the exponential growth into a linear relation:

This is why the rising part of the distribution appears approximately as a straight line when plotted on a logarithmic scale. The probabilities themselves are not growing linearly. The logarithm converts the underlying exponential shell growth into an approximately affine relation in x.

Logarithmic probability plot of the Rubik’s Cube shell distribution. The early shells appear nearly linear on a log scale because exponential shell growth becomes linear after taking logarithms. The bend near the outer shells marks the point where collisions between paths and the finite diameter of the cube graph begin to dominate.

The near-linearity visible in the early shells suggests that the cube graph initially behaves almost like a branching process before collisions between paths become dominant. At small distances, most move sequences still reach genuinely new states, so the shells expand rapidly. But as larger regions of the finite cube group become occupied, different paths increasingly lead back into already discovered states. The shell growth then slows, bends away from the linear trend visible on the logarithmic plot, and eventually collapses near the hard boundary at distance 20.

A linear regression using the exact shell probabilities up to distance 15 gives approximately:

Equivalently:

for a constant C´. The fitted branching factor 𝝀≈13.33 is very close to Korf’s asymptotic estimate 13.34847. This shows that the early shell growth is consistent with an expanding reduced branching process before finite-size effects begin to dominate the geometry of the graph.

Exact enumeration by breadth-first search

In principle, the exact distribution is obtained by breadth-first search (BFS) from the solved cube. Start with B₀={e}, then grow the balls recursively by:

where SBₓ={sg: s∈S, g∈Bₓ}. The new shell is the part of the next ball that was not already present:

So the exact algorithm is conceptually simple. Begin at the solved state, apply every legal move, record each newly reached position, and continue layer by layer:

distance[solved] = 0
queue = deque([solved])

while queue:
    state = queue.popleft()

    for move in legal_moves:
        new_state = move(state)

        if new_state not in distance:
            distance[new_state] = distance[state] + 1
            queue.append(new_state)

count_states_by_distance(distance)

This produces the shell sizes N₀,N₁,…,N₂₀, and therefore:

For a small puzzle, such as a 2×2×2 cube, or for a restricted move group, this direct procedure is realistic. For the full 3×3×3 cube, however, it is not. Be reminded that the full cube group contains about 4.3×10¹⁹ reachable positions, far beyond what a naive breadth-first enumeration can store or traverse.

This is why the proof of God’s number did not simply list all cube states by ordinary BFS. Rokicki, Kociemba, Davidson, and Dethridge (2010 ⇱) partitioned the cube space into cosets, used symmetry to reduce equivalent cases, and applied further reductions to make the computation feasible. Cube20 reports a partition into 2,217,093,120 sets, each containing 19,508,428,800 positions, later reduced by symmetry and set covering to 55,882,296 sets requiring solution.

Thus the distribution is defined by breadth-first shells, but the full cube cannot be handled by a naive traversal of those shells. The concept is elementary; the computation is not.

Monte Carlo approximation

If the full shell structure cannot be enumerated directly, one can estimate the distribution by sampling cube states. The ideal Monte Carlo procedure is simple in form:

histogram = {x: 0 for x in range(21)}

for _ in range(M):
    g = random_reachable_cube()
    x = optimal_distance(g)
    histogram[x] += 1

p_hat = {
    x: histogram[x] / M
    for x in range(21)
}

The crucial requirement is that optimal_distance(g) must return the true shortest solution length, not merely the length found by a fast human-like solver or a two-phase solver. Otherwise, the simulation estimates the distribution of a solver’s output lengths, not the distribution of optimal graph distances.

This is why optimal search methods matter. Korf’s 1997 method used IDA, or iterative-deepening A, together with pattern databases. Pattern databases precompute exact distances for subproblems and use those values as admissible lower bounds during search. Korf describes, for example, a corner-cubie table with 8!…3⁷=88,179,840 possible combinations, generated by breadth-first search from the goal. The stored value gives the number of moves needed to solve the corner pattern and therefore supplies a lower bound for the full cube.

The Monte Carlo estimator is:

where:

are sampled independently and uniformly from the cube group. By the law of large numbers:

For large M, the standard error is approximately:

This explains why common distances can be estimated well by random sampling, while distance 20 is extremely difficult to estimate directly. If p₂₀≈1/10¹¹, then even a billion random samples would usually find no distance-20 state. Rare tails require either enormous sampling, targeted construction, or structural enumeration.

The simulation below shows the same Monte Carlo idea on an exact corner-permutation subgraph of diameter 7, generated by the face turns U, R, and F, including inverses and half-turns. It is not the full 3×3×3 cube, whose diameter is 20, but a smaller cube-derived graph where the exact shell distribution is known and the sampling principle can be shown directly. The orange bars represent the exact probabilities obtained from breadth-first shell enumeration, while the blue bars show the empirical histogram produced by randomly sampled states. As the number of samples M increases, the empirical distribution converges toward the exact shell profile.

Monte Carlo convergence on a Rubik’s-cube subgraph. The animation shows how repeated uniform sampling recovers the shell distribution on a smaller cube-derived graph. Although this subgraph has diameter 7 rather than 20, it illustrates the same statistical principle: common shells are learned quickly, while rare boundary shells require far more samples.

Epilogue: What the Distribution Really Measures

We can now return to the original question in a more precise form. The probability that a random Rubik’s Cube position requires exactly x moves is not a question about how scrambled the cube looks, and it is not a Gaussian measure of accumulated disorder. It is the relative size of a distance shell in the cube graph.

That is the point of the derivation. Known shell counts and solver results already tell us where the probability mass lies. What the geometric argument adds is why those numbers form this particular shape. Near the solved state, the graph expands rapidly; farther out, different move paths begin to collide; and at distance 20, the distance profile reaches its hard boundary. The distribution rises, concentrates, and collapses because the finite Cayley graph itself has that structure.

So the article’s contribution is not a new count but a change of interpretation. It turns the probability table into a geometric profile of the cube group seen from the identity. A random cube is usually far from solved because most states lie in the large outer shells, while the hardest positions are rare because the distance-20 shell is only a thin boundary layer. The shape of the distribution is therefore the shape of distance itself.◼︎

👏 If you enjoyed this article, please fifty-clap and repost it to your network.

🔭 If you found value in this article and would like to support my ongoing scientific research and publication projects, you can do so here: https://ko-fi.com/samvaseghi