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.)

Comments

Post a Comment

Popular posts from this blog

How To Make ASCII Diagrams Beautifuller

Image
I've discovered an excellent tool in asciiflow.com .  The website makes it really easy to create ASCII box diagrams like this They put these things in fruit machines you know! This is ideal for source code banners, which I think should contain helpful documentation - but most programmers think it's a good place for the COPYRIGHT information and nothing else. But wait! we can make it beautifuller... and easier to read... by replacing some of the ASCII characters with ones available in UTF-8: There!  Isn't that better?  (Although some purists may object to non-ASCII characters in your code base.) SOURCE CODE: #!/usr/bin/python2 # coding: utf-8 # + gets converted in different ways depending on it's 4 neighbours # # . N . { nsew(N,S,E,W) has bit 3 set if N in "+|<>" # W + E { nsew(N,S,E,W) has bit 2 set if S in "+|<>" # . S . { nsew(N,S,E,W) has bit 1 set if W in "+-^v" # { nsew(N,S,E,W) has bit 0 set if E in
Read more

Calculation of ECS using simple convection model

Image
Contents Intro Simple stratified model Alternative convection model Tropospheric temperature gradient Approach used in convection model Calculation of Radiative Forcing from CO₂ increase Calculation of Radiative Forcing from H₂O increase Calculation of zero-feedback ECS Effect of including feedbacks Effect of water vapour Effect of cloud cover change Effect of sea ice loss Calculation of ECS including feedbacks Limitations One more thing: Changes to Troposphere depth Intro The goal of this post is to see if we can come up with an estimate of Equilibrium Climate Sensitivity using a simple model in which the atmosphere is treated as well-mixed.  By "simple" I mean that using the model will not require any advanced mathematics or computation, but will still be realistic enough to come up with an estimate within the likely range of 2.5 - 4.0°C predicted by the IPCC Assessment Report 6 .  I will try to take as little on trust as possible and show how the results are arrived at.
Read more

Why growth is falling in all developed countries (as a long term trend)

Image
In this post I argue that economic growth is not the normal state of affairs, it is a blip caused by the discovery of a one-off resource of non-renewable energy.   The logistic equation $$ \frac{dy}{dt} = y(1-y) $$ Here's a simple model.  Humans discover an exploitable but limited resource and start consuming it.  The amount consumed, $y(t)$, is a function of time.  The general form of the equation is $\frac{dy}{dt} = \alpha y (\beta - y)$, but if you choose the right units $\alpha$ and $\beta$ both become $1$. Why should this work, in principle? Early on, the factor $1-y$ is approximately $1$ and can be ignored.  So the model states that annual consumption $dy/dt$ starts off proportional to $y$.  In other words, $y$ grows exponentially at first.  This could happen if exploiting the resource enables further exploitation of the resource.  For example, suppose a few humans are shipwrecked on an island with 1000 trees: they take ages to cut down the first tree as they are using their
Read more