Algebra

Every position of the pocket cube

The two-by-two Rubik's cube has 3,674,160 positions once its orientation in the hand is ignored, few enough to visit every one. Breadth-first search finds that none is more than eleven face turns from solved, or fourteen quarter turns, and that only 2,644 positions sit at that distance. Counting move sequences proves only nine; the gap between nine and eleven is the cube's relations, the first of which appear at three turns. Two faces alone reach 29,160 positions, arranged by a copy of the symmetric group on five things acting on six corners.

Worth reading first: The group drawn as a map · How fast the ball fills.

The two-by-two Rubik’s cube, sold as the pocket cube or the mini cube, has eight corner pieces and nothing else. Every face turn moves four of them and twists some, and any position can be scrambled from solved and solved again by turning faces. That makes the set of positions a group: a position is the rearrangement that produced it, two positions compose by doing one rearrangement after the other, and every rearrangement can be undone. The group drawn as a map explained how to draw such a group: one dot for each element, one arrow for each generator, and multiplying by a generator becomes walking along an arrow. For the pocket cube the generators are the face turns, the dots are the positions, and the number of turns needed to solve a position is its distance from solved in the drawing.

The interesting thing about the pocket cube is its size. It has exactly 3,674,160 positions, few enough that a computer can visit every one of them and record its distance, so the questions that are open for the full three-by-three cube for decades — how far apart can two positions be, how many positions are at each distance — have exact answers here that take a few seconds to find. This essay finds them, and then asks what the answers show about the group: why counting alone cannot give the right number, where the group’s relations begin, and what happens when the turns are restricted.

Three million six hundred and seventy-four thousand

The farthest a pocket cube can be from solved. antipode F2 U' R U' R F2 R F' U2 R' U'; faces with 3,3,3,3,3,3 colours
Fig. 1 The solved cube and one of the positions farthest from it, eleven face turns away, with one shortest way there under it.

The count is a short calculation. The eight corner pieces can be put in their eight places in 8!=40,3208! = 40{,}320 orders, and each piece can sit in its place in three twists, which would give 383^8 twists in all. But not every twist pattern is reachable. Measure each corner’s twist as 0, 1 or 2 relative to its home orientation; then a turn of the up face moves four corners without twisting any, and a turn of the right or front face twists the four corners it moves by 1, 2, 1, 2 in some order, which adds up to 6. So every turn preserves the total twist modulo 3, and the reachable positions have total twist 0: once seven corners’ twists are chosen, the eighth is forced. That leaves 8!⋅37=88,179,8408! \cdot 3^7 = 88{,}179{,}840 arrangements.

There is one more thing to remove. A pocket cube has no fixed centres, so a cube that has been turned as a whole in the hand looks like a different position and is not one. Twenty-four ways to set a cube down counted the rotations of a cube; dividing by them gives 88,179,840/24=3,674,16088{,}179{,}840 / 24 = 3{,}674{,}160. The tidy way to divide is to hold one corner still — here the down-back-left one — and turn only the three faces that do not touch it: up, right and front. Each turn of a face that does touch it is the same, after a whole-cube rotation, as a turn of the opposite face, so nothing is lost.

That gives nine generators in the usual way of counting: a quarter turn of each face either way, and a half turn of each face, which counts as one move. In the figure, the solved cube sits beside one of the positions that the search finds farthest from it. Every face of the drawn position shows three colours, though, as the section on the farthest positions explains, looking disordered is not what makes a position far.

The computation behind every figure here is a breadth-first search. Start with the solved position at distance 0. Apply all nine turns to it: the nine new positions are at distance 1. Apply all nine turns to each of those: whatever is new is at distance 2. Continue until a round finds nothing new. Each position is stored as a pair of numbers — the arrangement of the seven movable corners, one of 5,040, and the twists of six of them, one of 729 — and each turn is a pair of lookup tables, so the whole search takes about a second.

Eleven turns, and what counting says

The search finds the hero’s numbers. One position at distance 0, nine at distance 1, then 54, 321, 1,847, 9,992, 50,136, 227,536, 870,072, 1,887,748, 623,800 and finally 2,644 at distance 11, after which nothing new is found. Every position is solved in at most eleven face turns, and 2,644 of them need all eleven. Counting quarter turns only, the second panel’s search finds the farthest positions at distance 14, and there are just 276 of them.

Before the search, one could ask how much of this could be predicted without it, by counting move sequences. A sequence of kk turns that is any use at all never turns the same face twice in a row, since two turns of one face combine into one or into nothing. The first turn can be any of nine, and each later one any of the six turns of the other two faces, so there are at most 9⋅6k−19 \cdot 6^{k-1} useful sequences of length kk, and at most that many positions at distance kk. The dashed line in the hero is this bound. Adding it up, sequences of length at most eight number

1+9+54+324+1,944+11,664+69,984+419,904+2,519,424=3,023,308,1 + 9 + 54 + 324 + 1{,}944 + 11{,}664 + 69{,}984 + 419{,}904 + 2{,}519{,}424 = 3{,}023{,}308,

which is fewer than 3,674,160. So some position must need at least nine turns: counting proves nine. The truth is eleven, and the difference between nine and eleven is not a failure of the counting so much as a measurement of everything the counting ignores. The sequences are counted as if each one reached a different position, and they do not.

Positions at each distance in quarter turns. 0:1/1 1:6/6 2:27/30 3:120/150 4:534/750 5:2256/3750 6:8969/18750 7:33058/93750 8:114149/468750 9:360508/2343750 10:930588/11718750 11:1350852/58593750 12:782536/292968750 13:90280/1464843750 14:276/7324218750
Fig. 2 The same search in quarter turns. Counting sequences that never undo the previous turn proves that some position needs ten; the farthest need fourteen, and 276 positions do.

The quarter-turn version shows the same pattern with different numbers. A useful sequence never follows a turn with its own inverse, so there are 6⋅5k−16 \cdot 5^{k-1} of length kk, and summing them shows that sequences of length up to nine cannot cover the group: counting proves ten, the search finds fourteen. The two metrics answer slightly different questions — whether a half turn is one move or two — and they disagree on which positions are farthest, but they agree on the shape. The spheres grow by a factor of about five or six at each step while there is room, peak near three quarters of the way out, and then collapse abruptly into a small set of antipodes. It is the profile how fast the ball fills would predict for a group that looks like a tree up close and is finite: exponential growth that has nowhere to go.

Where the coincidences start

Where move sequences start to coincide. U2 R2 U2=R2 U2 R2; U2 F2 U2=F2 U2 F2; R2 F2 R2=F2 R2 F2; shares 1.0000,1.0000,1.0000,0.9907,0.9501,0.8567,0.7164,0.5419,0.3453,0.1249,0.0069,0.0000
Fig. 3 The share of move sequences of each length that reach a new position. All sequences of one and two turns do; three pairs of three-turn sequences coincide; by eleven turns almost none do.

If every useful sequence reached a different position, the group would look exactly like a tree out to the distance where it ran out of room. Comparing the two counts at each length measures how far that is from true, and the figure plots the ratio: the number of positions at distance kk divided by the number of useful sequences of length kk.

Out to two turns the ratio is 1. Every sequence of one or two turns ends somewhere different. At three turns there are 324 useful sequences and 321 positions, and listing the sequences by where they end shows that three positions are reached twice, each by a pair of sequences made entirely of half turns:

U2R2U2=R2U2R2,U2F2U2=F2U2F2,R2F2R2=F2R2F2.U^2 R^2 U^2 = R^2 U^2 R^2, \qquad U^2 F^2 U^2 = F^2 U^2 F^2, \qquad R^2 F^2 R^2 = F^2 R^2 F^2.

These are the cube’s first relations — equations between words in the generators that hold in the group but not in the free group on the same generators. They have the shape of the braid relation, aba=bababa = bab, and in fact they say that the two half turns U2U^2 and R2R^2 generate a group in which (U2R2)3(U^2 R^2)^3 is the identity: the half turns of two faces are like two reflections whose product has order three. The figure’s companion sequences show that the half-turn subgroup is tiny, as the next section will measure.

At four turns 1,944 sequences reach 1,877 distinct positions, and thirty of those positions were already reachable in fewer turns, so only 1,847 are new: 95.0% of sequences find a new position. The share then falls quickly — 71.6% at six turns, 34.5% at eight, 12.5% at nine — and at eleven turns only 2,644 of 544,195,584 sequences reach a new position, about one in two hundred thousand. Most long sequences end at a position that a shorter sequence already reaches, which is the same thing as saying most long sequences are inefficient ways to scramble the cube.

This is the general reason the counting bound is weak. It assumes the Cayley graph is a tree, and a finite group’s Cayley graph is full of cycles: every relation is a cycle through the identity, and every cycle through the identity can be translated to start anywhere. The edge that is as big as the ball measured how much of a tree’s ball lies on its boundary; the pocket cube’s graph begins like a tree with branching six and starts closing on itself at three turns. The diameter is the distance at which the ball, growing by less than the tree’s rate because of these cycles, finally fills the group. Counting sequences gives the distance at which a tree with the same branching would hold the group’s number of points, and the cycles cost two more turns on top of that.

The farthest positions

The 2,644 antipodes are worth a moment on their own. They are the positions for which no sequence shorter than eleven turns works, and they are less than a thousandth of the group. Since the search records every position’s distance, a shortest solution of any of them can be read off directly: from a position at distance dd, some turn leads to a position at distance d−1d - 1, and following such turns gives a shortest solution. Reversing the solution and inverting each turn gives a shortest scramble, which is what the first figure prints under its antipode.

The farthest positions are not the most disordered in any obvious sense. The drawn one shows three colours on every face, but so do great numbers of positions much nearer to solved, and how scrambled a position looks is a poor guide to how many turns it needs. Distance in a Cayley graph is a property of the whole group’s structure and not of how messy a position looks; thirty-one moves from solved found the same thing for the eight-tile sliding puzzle, whose farthest positions are also scarce and also do not look special.

There is a symmetry that guarantees the antipodes come in families. The cube’s own symmetries that fix the held corner — the rotations about the corner’s diagonal, and the reflections — permute the faces up, right and front, and they send positions at distance dd to positions at distance dd. So do inversion, which sends a position to the position that undoes it, and conjugation by any whole-cube symmetry. The 2,644 antipodes therefore split into orbits of these operations, and the 276 quarter-turn antipodes likewise; one antipode found by the search stands for a whole family of them. In the eight-tile puzzle there were two farthest positions; here there are thousands, but they are still a vanishing share of a graph whose spheres are bunched around distance nine.

The average distance from solved is 8.76 face turns; more than two thirds of all positions are at distance nine or ten, and 92% at eight, nine or ten. A randomly scrambled pocket cube is, therefore, almost certainly nine or ten turns from solved, and the antipodes are a thin shell on the far side of the bulk of the group. That shape — a tightly concentrated distribution of distances with a short tail on either side — is shared by the full Rubik’s cube, whose antipodes are at twenty face turns and whose typical scrambled position is eighteen turns from solved.

Two faces, and a copy of five things acting on six

Fewer faces, fewer positions, longer distances. all 1,9,54,321,1847,9992,50136,227536,870072,1887748,623800,2644; UR 1,6,18,53,148,400,910,1882,3276,4628,6198,6325,4352,941,22; half 1,3,6,9,5
Fig. 4 Distances from solved when every face may turn, when only the up and right faces may, and when only half turns are allowed. The smaller the toolkit, the smaller the group, and the farther its own farthest position.

Restricting the turns gives smaller groups. Turning only the up and right faces reaches 29,160 positions, and the search finds the farthest of them fourteen face turns from solved — three more than the whole group needs, although the subgroup is 126 times smaller. Using only the three half turns reaches just 24 positions, the farthest four half turns away. Each set of reachable positions is a subgroup, and the blocks a subgroup cuts out explained why each size divides the size of the group containing it: Lagrange’s theorem says the subgroup’s copies, translated around, tile the group exactly. So 24 divides 29,160 (1,215 times) and 29,160 divides 3,674,160 (126 times).

The figure shows the cost of a smaller toolkit. A position reachable with the up and right faces alone may still have a shorter solution that uses the front face, so the distance inside the subgroup is never less than the distance in the whole group and is often more. On the full Rubik’s cube, solvers know this as the price of two-generator algorithms: they are easy to perform and long. The pocket cube shows the price exactly — up to three extra turns.

The up-and-right subgroup also hides the most surprising structure in this essay. Those two faces touch six of the eight corners, and the six can in principle be arranged in 6!=7206! = 720 ways, with twists on top. The search shows that only 120 arrangements occur, combined with all 353^5 legal twist patterns: 120×243=29,160120 \times 243 = 29{,}160. And the 120 arrangements are very special. For any three of the six corners and any three places, exactly one arrangement sends the first three to the second three in order — the group is sharply three-transitive on six points. There is essentially one group of order 120 that acts that way: the group of maps x↦(ax+b)/(cx+d)x \mapsto (ax + b)/(cx + d) of the projective line over the five-element field, whose six points are 0,1,2,3,40, 1, 2, 3, 4 and ∞\infty. That group is isomorphic to the symmetric group on five things, S5S_5.

So the arrangements that two faces of a pocket cube can make are a copy of the permutations of five objects, acting on six corners in an unexpected way. Nothing about the cube mentions five of anything; the five appears because the two four-cycles that the faces perform, sharing two corners, generate precisely the projective group of a line with six points. It is an instance of something two random shuffles reach every shuffle noticed from the other side: two permutations almost always generate everything, and when they do not, what they generate is usually a structure that has a name.

How often a sequence comes back

How often a sequence must be repeated. 1:1 2:3843 3:40418 4:56700 5:40824 6:521766 7:524880 9:215460 10:122472 12:657720 15:326592 18:714420 30:244944 36:204120
Fig. 5 All 3,674,160 positions by order — how many times a position’s sequence must be repeated before the cube is solved. The largest order is 36.

Any move sequence, repeated, eventually returns the cube to solved, because the group is finite and the powers of an element cannot all be different. The number of repetitions needed is the sequence’s order, and it depends only on the position the sequence produces, not on the sequence. It can be read from the position directly. The corners fall into cycles — each corner moved to the place of the next — and a cycle of length mm returns its corners to their places after mm repetitions. If the twists picked up around the cycle add up to a multiple of three, the corners come back untwisted then; otherwise they come back twisted and need three times as many repetitions. The order is the least common multiple of these numbers over all the cycles.

The figure counts every position by its order. The commonest orders are 18, 12, 7 and 6, each held by between 14% and 20% of the group. Order 7 is a seven-cycle of the movable corners, which twist with total 0 automatically when the seventh is forced. The largest order is 36, held by 5.6% of positions: a four-cycle of twisted corners, needing twelve repetitions, together with a three-cycle of twisted corners, needing nine, whose least common multiple is 36. A five-cycle with a twisted three-cycle would give 45, but that would need eight movable corners and the held corner has to stay put, so 36 is the ceiling. Only 3,843 positions have order 2, and only one — solved — has order 1.

Order is a fact about cycles in the Cayley graph, as distance is a fact about paths. Repeating a sequence traces a closed walk through the drawing that comes home after the order’s number of laps. The relations of the third section are the shortest such cycles; the orders here are the cycles that a single element generates. Repeating a shortest sequence for a position at distance dd gives a closed walk of length dd times the order, and the figure is a census of the loops that single elements generate.

What the search cannot show

The search answers every question about the pocket cube that can be phrased as a property of individual positions, and it says almost nothing about why the answers are what they are. It finds the diameter, eleven, but no argument that would have predicted eleven rather than ten or twelve; the counting bound gives nine and nothing gives more without the search. It finds 2,644 antipodes, but no description of them that does not amount to listing them. This is the usual trade of exhaustive computation, and how fast the ball fills stated it from the other side: growth rates are invariants of a group that survive a change of generators, while diameters and sphere sizes depend on exactly which generators are chosen. The half-turn and quarter-turn metrics give different diameters for the same group, and neither is more correct.

Nor does the picture scale. The full Rubik’s cube has about 4.3×10194.3 \times 10^{19} positions, far beyond any table, and its diameter of twenty face turns was settled in 2010 by a computation that split the group into cosets of a large subgroup and searched each coset cleverly, using about thirty-five years of processor time. The pocket cube is the size of group where the naive search is a few seconds, and that is the whole reason its answers are exact. The method that settled the big cube — divide by a subgroup, search the cosets — is Lagrange’s theorem used as an algorithm, and the up-and-right subgroup here, with its 126 cosets, is a small version of the same decomposition.

What the counting can show and the search cannot is a lower bound for every group of the same kind. Any group generated by nine moves in three families, and holding as many elements as the pocket cube, must have diameter at least nine; that is a theorem about the shape of trees. The search shows that this particular group needs two turns more, and the coincidences explain where those two turns go: into the relations that make a finite group’s Cayley graph close up on itself.

Still open: the middle of the distribution, for larger cubes

For the four-by-four cube and larger, even the diameter is unknown; the best bounds are far apart, and no search of the whole group is possible. The pocket cube’s distribution — a sharp peak near three quarters of the diameter and a thin shell of antipodes — is conjectured to be typical of these puzzle groups, but the shape of the distance distribution for a large puzzle group is not something any theorem predicts. The same question was asked of random walks on groups, where the long-run behaviour is controlled by a single number. For the distance distribution of a specific finite group with specific generators, no such number is known, and the pocket cube remains one of the few puzzles for which every distance has been measured.

What links here

Computed from the collection, not written here: the essays that point at this one.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A dashed tag is an object no other essay names yet.

Cayley graphExhaustive searchGroupLagrange theoremOrder of an elementSubgroupWord metric