Rubik's Cube

About 18 years ago a friend patiently explained to me how to solve a Rubik's Cube.  I memorized the instructions, but realized sooner or later I'd forget them.  So maybe a week later I wrote up my notes using dia, and printed them out.  Since then I've carried this same slip of paper around in my wallet, for those occasional opportunities when you're 'round someone's house and you spot a cube exhibiting a frustratingly high degree of entropy.

It's still just about legible

Each face of the cube is given a letter

• U - up
• D - down
• F - front
• B - back
• L - left
• R - right

A single letter on it's own represents rotating the face 90$^\circ$ clockwise (looking at the face), and a letter followed by an apostrophe means rotate anti-clockwise.  Thus LL' is the same as doing nothing.  An exponent of 2 simply means do the preceeding action twice.  Below, I've split the sequences into subblocks with dashes to make them easier to memorize$^\dagger$.

HOW TO SOLVE THE CUBE

1. Move the top 8 cubes to the correct positions (note 8 cubes not 9, because the centre of each face is already in the correct position)
2. Use the sequence DL-D'L'-D'F'-DF to move centre-edge cubes between the bottom row and the middle row without disturbing the top row, as shown in the 1st diagram.  (You may need to use the reflected version D'R'-DR-DF-D'F').  Use this move multiple times to complete the middle row.
3. Turn the cube over so that now the bottom and middle rows are complete and the top row remains.
4. The goal is now to make the top face display a George Cross, without worrying about whether the middle edge pieces on the top row are in their ultimate positions.
5. If you start with a back-to-front "L" shape as in the 2nd diagram use the sequence FUR-U'R'F'.  This will result in a cross shape on the top row without disturbing the bottom and middle rows.
6. If you start with a line as in the 3rd diagram use the sequence FRU-R'U'F'.
7. The next goal is to ensure that the top corner pieces are in the correct positions, ignoring their orientation.  The sequence LU'-R'U-L'U'-RU$^2$ swaps two corner pieces (as shown in diagram 4) without disturbing earlier achievements.
8. You must now orient the corner pieces correctly.  The sequence shown in diagram 5 is RU-R'U-RU$^2$-R'U$^2$.  This rotates 3 corner pieces clockwise by 120$^\circ$ leaving the other piece - and all previous achievements - unaffected.
9. You must now place the top middle-edge pieces in the correct locations.  To do this use the sequence for the last diagram R$^2$UFB'-R$^2$F'B-UR$^2$, which rotates the positions of 3 middle edge pieces without changing the colour that is facing up, or the results of any previous step.

I noticed a few years after I made my careful notes that new Rubik's Cubes now come with instructions for solving them!  And of course you can now learn how to do it from YouTube videos if you want.  How annoying - I am no longer special!

ARE THESE INSTRUCTIONS COMPLETE?

A natural question arises: are these rules always sufficient?  I.e. can you use them to solve the cube starting from any initial state?

It doesn't take very much thought to realise that it is always possible to complete the first two rows using rules 1 & 2 above.  Also, using rule 7 repeatedly it is always possible to get the corner pieces in the last row into the right positions.  However, after that our luck runs out.

Rules 5 and 6 both flip two of the centre-edge pieces in the final row.  This means that they cannot take you from and odd number of centre-edge pieces with the correct colour up, to an even number.  Likewise, the sum of rotations caused by rule 8 is 360$^\circ$, so it isn't going to help you if only one corner piece is rotated - however many times you use it.  There's a similar problem with rule 9, although it is a bit more subtle to describe$^{\dagger_2}$.

The interesting thing is that unless someone has taken the cube apart and put it back incorrectly, these potential problems never actually occur, and rules 5, 6, 8 & 9 are always sufficient to complete the relevant stage.  How is it that these pathological situations never arise?  To understand that we need to understand a bit about permutations.

A permutation is a one-to-one and onto mapping from a set such as $\{1,...,n\}$ to itself.  In that particular case the set of permuations is known as $S_n$ and is a group under the operation of function composition.  (NB: the group operation is usually defined as function composition back-to-front, so if $\sigma, \rho \in S_n$ then applying the $\sigma\rho$ means applying $\sigma$ first, then $\rho$).

A cycle is a special permutation where some numbers are placed in a circle and each mapped to the neighbour on their right, whilst all the other numbers are just mapped to themselves.  The notation for this is just a list of numbers between parentheses, for example $(3 4 1 9)$ maps 3 to 4, 4 to 1, 1 to 9, 9 to 3, and every other number to itself.  It's fairly easy to prove that every permutation can be written as a product of disjoint cycles.  In the picture above I've labelled the stickers on the centre-edge pieces with numbers from 1 to 8 and shown the permutation corresponding to the move U.

Once you have shown that every permutation can be written as a product of cycles it follows straightforwardly that every permutation can be written as a product of transpositions (i.e. pair swaps), since e.g. $(1 2 3 4) = (1 2)(1 3)(1 4)$.  However, it is an odd fact (and only slightly harder to prove) that any given permutation can be written either as a product of an odd number of transpositions, or as a product of an even number, but not both.  This allows us to define permutations as odd or even.

In the diagram above we can see that a rotation of one face - if we think of it as a permutation of the cube's centre-edge stickers - is an even permutation.  The product of even permutations is always even and so, however badly you mess up the cube you will always end up with an even permutation, never an odd one.  This means that (at least) half of the permutations of the cube can never be reached unless you take the cube apart.

This explains how it is possible that, although the rules seem to only help in some situations, the other situations never arise!

OTHER TYPES OF CUBE

Occasionally you see 2x2x2 cubes.  Luckily there's no need for a new set of instructions for these, you simply have to imagine they're actually 3x3x3 but that the 3 middle rows are infinitesimally narrow and then the rules above still work (although, you can skip some steps).

4x4x4 cubes are a little trickier, however it's still possible to reuse the rules above.  The trick is to combine the middle pieces into 2x2 and 2x1 superblocks and then solve using the 3x3x3 cube rules.

FOOTNOTES

• ($\dagger$) I've just discovered this is called "chunking" and is recognised by psychologists as a helpful tool for memory.  You can have up to 7 items in one chunk, but my memory isn't as good as that so I've opted for a maximum of 4 (not including apostrophes and 2s).
• ($\dagger_2$) Rule 9 can only generate even permutations of the stickers.  (Even-ness is described later on.)