Rubik’s Cube

Rubik’s Cube, solved

The classic Rubik’s Cube. The one that started it all. The 3x3x3 face-turning magic cube. Though universally known as the Rubik’s Cube, it is sold under a bewildering array of brands and names, often under the generic term 3x3x3; for example Shengshou 3x3x3, Alpha 3x3x3, etc. Furthermore the search for the perfect speedcube has resulting in many brands releasing entire series of Rubik’s Cube; for example Alpha I, Alpha II, Alpha III, Alpha IV, and Alpha V.

As with all the face-turning cube puzzles, the inner core has octahedral symmetry, with turning axes aligned with the axes of rotational symmetry that pass through opposite faces of the cube shell. These axes are a generating set for the isometries of the cube, so this is a puzzle where it is possible to manipulate any piece into any isometric position. (This is pretty much a prerequisite to a puzzle being really hard, and the Rubik’s Cube certainly is that)

Number of positions

Rearranging stickers

A naive attempt to calculate the number of possible positions might go something like this: there are six faces, and each face is divided into nine little squares, so in total there are 54 squares. Each square can be any of six different colours, so the total number of positions is 654, which is slightly more than 1000000000000000000000000000000000000000000. This is actually the number of combinations you can make if you have a blank cube and an unlimited supply of stickers in all six colours.

Suppose we restricted ourselves to exactly nine stickers of each colour, as when we randomly rearrange the stickers on a Rubik’s Cube. Let’s put the white stickers on first. We have 54 blank spaces, and we have to choose nine of them to receive white stickers. In the notation of combinatorics, we write the number of ways to choose 9 from 54 as 54C9. Having chosen our white squares, there are 45 squares remaining, and we need to choose nine of them to receive yellow stickers. The number of ways we can do that is 45C9. And so it goes until we have only nine squares left, and one colour to go, in which case we have no choice left. The total number of ways we can re-sticker our cube is

54C9 × 45C9 × 36C9 × 27C9 × 18C9

This number can be calculated according to the formula

aCb = a!b!(a-b)!

When we apply this to our formula, most terms cancel out, and we end up with 54!9!9!9!9!9!9!, or slightly more than 100000000000000000000000000000000000000. (That may look the same as the previous number, but it has 4 fewer zeros, so it is smaller by a factor of 10000.)

This is the number of positions we can make by moving stickers around. But it is easy to see that this includes many positions that cannot be obtained by turning faces. Three examples:

  1. In a correctly stickered cube, each centre square is a unique colour, and no combination of face turns can change that. Yet by swapping stickers around, one can assign the same colour to more than one centre square
  2. In a correctly stickered cube, each edge piece has two different coloured stickers; but by swapping stickers around one can assign the same colour to both squares on an edge piece. Similarly, each corner piece should have three different colours on it, but swapping stickers can violate this.
  3. If white and yellow are opposite faces, then a correctly stickered piece cannot contain both colours.

Rearranging pieces

In order to calculate the number of positions a cube can be put in using only legal moves, we need to think in terms of pieces, not stickers. There are three kinds of piece:

  1. The six centre pieces are fixed — they can be rotated but not moved, and centre rotations are irrelevant for solving the standard Rubik’s cube.
  2. There are 12 edge pieces, each with two coloured faces. Each piece can be placed in each of the 12 edge positions, in two different orientations.
  3. There are 8 corner pieces, each with three coloured faces. Each can be placed in each of the 8 corner positions, in three different ways.

Based on this, we might calculate the number of positions as follows:

  1. Forget the centre pieces; these are fixed.
  2. Randomly choose an edge piece. There are 24 different ways it can be placed and oriented. Place it somewhere. Choose the next piece; one of the 12 places is now taken, so there are 22 different ways the second piece can be placed and oriented. And so on, resulting in 24 × 22 × 20 × 18 × 16 × 14 × 12 × 10 × 8 × 6 × 4 × 2 positions for the edges. This is a little more than 2000000000000 (two trillion in the short scale).
  3. Now do the same with the corner pieces: there are 24 different ways the first can be placed and oriented. Once that is in place there are only 7 positions left, so the second piece can be placed and oriented in 21 different ways. And so on, resulting in 24 × 21 × 18 × 15 × 12 × 9 × 3 positions for the corners. This is just over 44 million; 44089920 to be precise.

Multiply these two figures together, and you get a little over 500000000000000000000 — in the short scale this is 500 quintillion or about half a sextillion.

Turning faces

Rubik’s Cube, thoroughly scrambled

But we still haven’t arrived at the correct number of positions reachable by legal turns. The number we have calculated is the number of positions that can be reached if you break a cube down to its core and then put it back together again. Some positions can be reached that way, but cannot be reached if you leave the cube intact and make only turning moves.

To demonstrate this, take a scrambled cube and solve just one edge piece — that is, place that one piece, correctly oriented, in its correct position between its corresponding centres. Now make a series of turns that move that piece around and ultimately put it back, correctly oriented, where it belongs. Count the number of quarter turns you made. You will find it is an even number. Always.

Now do the same thing, but this time put the piece back where it belongs, but flipped in orientation. You will find that flipping an edge piece always requires an odd number of turns.

This rule applies for all pieces and all positions. On my cube, for example, moving the orange-green edge from its solved position to the white-red position (orange on the white face, green on the red face) always requires an even number of quarter turns. Putting it there the other way around always requires an odd number of quarter turns.

Now suppose you sat down with a scrambled cube and looked at each edge piece and figured out whether its distance from its solved position was odd or even. One thing you would find is that there will always be an even number of edge pieces that are an odd distance from their solved position. Why is this?

Rubik’s Cube, nearly solved. Five edges are solved, six are one quarter turn from solved, and one is two quarter turns from solved — a sum of eight.

To answer that, start with a solved cube. Every edge piece is solved, so each edge piece is zero quarter-turns away from where it should be. Add up all those zeroes, and you get zero. Now turn one face by one quarter turn. After that, eight edges are still solved, but four edges are 1 quarter-turn away from solved. Add up those eight zeroes and the four ones and you get a total of 4. Now choose a face and make another quarter turn. There are a whole lot of ways you can do that, but when you’re done, the sum of edge piece distances from solved will be 8 (or 0 if you simply reversed the first move). Make another turn, and another. With every turn, you leave eight edges unchanged, and you move four edges by one quarter turn, increasing or decreasing their distance from solved by one. So when you add up all the distances you’ll always get a multiple of four.

So now you know why you will always have an even number of edge pieces that are an odd distance from solved: because if you had an odd number of edge pieces that were an odd distance from solved, they would all add up to an odd number, which wouldn’t be a multiple of four, and this is impossible using only face turns.

This also explains why you will never find a cube that is solved except for one misoriented edge. It’s a clear case of odd parity, and that’s impossible.

This is only one example of a parity issue. There is another parity issue with edges, and also parity issues with corners. These are much harder to illustrate though, so I won’t go into them. Suffice it to say that parity issues render 11 out of every 12 positions unreachable, so the number of positions reachable through turns is one twelfth of the number of positions reachable by breaking a cube down and reassembling it: a total of 43252003274489856000.

Orbits

Another way of looking at this is in terms of orbits. The Rubik’s Cube has twelve of them. Each orbit contains 43252003274489856000 positions, and no position belongs to more than one orbit. One of the twelve orbits contains the solved position in it, and as long as you only turn faces you will always remain within that orbit. But break it down and put it back together with one edge flipped, and you’ve put the cube into a different orbit. You’ve unlocked 43252003274489856000 new positions, but you’ve rendered unreachable the 43252003274489856000 positions of the solvable orbit, including the solved state. Until you break it down again, your cube will stay in that orbit, and you will never be able to solve it.

God’s Number

God’s Algorithm is the tongue-in-cheek name for an ideal set of instructions for solving the Rubik’s Cube. God’s Algorithm always solves the cube in the smallest possible number of turns. The maximum number of turns that God’s Algorithm would take is called God’s Number — even God couldn’t guarantee to solve a cube in fewer moves that then, because some positions cannot be solved with fewer moves even with God’s Algorithm.

In mathematical terms, God’s Algorithm would always find the shortest path through the Cayley Graph of the Rubik’s Cube Group, and God’s Number is the diameter of that Cayley Graph.

A Rubik’s Cube in the ‘superflip’ position cannot be solved in fewer than 20 turns.

A great deal of research has been undertaken in this, and the number has only recently been settled as 20 in the half-turn metric. This means that no matter how scrambled your cube is, it will always be possible to solve it in 20 moves or less, where full half-turn counts as one move not two. Personally I’m much more interested in knowing God’s Number in the quarter-turn metric. This is currently unsolved but known to be between 26 and 29. Most likely it is 26.

There are millions of positions that require a full 20 half-turns to solve, probably hundreds of millions. One well-known example is the position known as the superflip: a cube that is solved except that every edge is misoriented.

Variations and related puzzles

There are more variations on the Rubik’s Cube that any other puzzle. Of course you could argue that the entire twisty puzzle industry is based on on variations of the original, but let’s be a little narrower and look at variations based on the same inner core

Shell variants

One way of creating a Rubik’s Cube variant is to use the same core, and make basically the same cuts, but apply them to a different shell. There are a vast number of these, and many are thoroughly unremarkable.

The Dipyramid looks interesting and novel, but its really just a dipyramid shell careless clapped onto a Rubik’s Cube core with no regard for its natural symmetries.

Rubik’s Cube cores have been put inside shapes that have no symmetry whatsoever, such as Batman heads. These jumble on every move. At least they are honest — they are explicitly, openly asymmetric. Worse are the puzzles that put a Rubik’s Cube core inside with a polyhedron shell with no common symmetries. These too jumble on every move. Examples include the Threefold Hexagonal Prism and the Dipyramid. Both superficially appear to be novel puzzle shapes, but their symmetries are not mapped onto the symmetries of the Rubik’s Cube core at all. They might as well be Batman heads.

There are several exceptions: variants in which the shell symmetries map onto the core symmetries in interesting ways:

  • The 12 Face is similar to the Rubik’s Cube but has different requirements for orientation of pieces.

    The 12 Face (horribly misnamed the Super Skewb by LanLan — it is definitely not a Skewb) is a vertex-turning rhombic dodecahedron puzzle with a Rubik’s Cube core. Since the rhombic dodecahedron has the same rotational symmetry as the cube, this is a non-jumbling puzzle. What makes it different to the Rubik’s Cube is that the Rubik’s Cube centres correspond to the order-four vertices in the 12 Face, so it becomes essential that they be oriented correctly. On the other hand, Rubik’s Cube edges correspond to the 12 Face’s face centres, so their orientation doesn’t matter… until you get to endgame and discover you have a parity error!

  • The Master Pyramorphix is the crème de la crèmeof Rubik’s Cube variants.

    The Master Pyramorphix (or Mastermorphix) is the crème de la crème of Rubik’s Cube variants. It is an edge-turning tetrahedron puzzle, and since a tetrahedron has six edges, it must have six turning axes. This is exactly what the Rubik’s Cube core offers, but the Rubik’s Cube core provides for 90° rotations, whereas the tetrahedron has only 180° rotational symmetry about its edge centres. This discrepancy gives the Master Pyramorphix its charm: you can scramble it using only 180° turns, in which case it retains its tetrahedron shape, and can be solved using only 180° turns. Or you can scramble it using 90° turns, in which case it jumbles, and all of the complexity of the Rubik’s Cube is unlocked.
  • Fisher’s Cube aligns 90° turning axes with axes of 180° rotational symmetry.

    Fisher’s Cube puts a Rubik’s Cube core inside a cube shell, but instead of aligning the turning axes with face centres, it misaligns the shell by a 45° rotation, so that only two of the turning axes pass through face centres. The other four axes pass through edge centres These are axes of rotational symmetry for the cube, but only for 180° rotations rather than 90° rotations. Thus some rotations preserve the cube shape, while others jumble it.

Related puzzles

The Rubik’s Cube is the 3x3x3 in a long series of magic cube puzzles, ranging from the 2x2x2 Pocket Cube, through the 4x4x4 Rubik’s Revenge and the 5x5x5 Professor’s Cube, and beyond. There are also cuboids with a non-cubic aspect; for example the 2x3x4.

Techniques and algorithms for solving the Rubik’s Cube generally apply to three-layer face-turning puzzles of other shapes, for example the dodecahedron puzzle Megaminx.