Rubik's Cube

Point of order: I'll probably end up referring to Rubik's Cube as :
  • Rubiks Cube (apostrophes ashmostrophes)
  • The Rubik's Cube (*shudders*)
  • RC (I really can't be bothered typing right now)
  • The Cube (Let's be honest, there is only one spinny cube puzzle)
  • It (In French or German it's a 'him')
  • Assorted other things

Rubik's cube is a 'rabbit hole'.
A child can play with one but the more you learn the harder it gets.
What follows is an eye-bleeding trip down that rabbit hole. Alice falling down the rabbit hole

Caveats:
To be Alice you ideally need to be able to solve a cube already and have an 'A level' grasp of Mathematics.
But if I've done my job correctly any Alice will be fine.

And full disclosure: There is no neat 'closed form' magical equation which solves the cube.
Modern 'optimal' solvers use tables of information that took immense amounts of time to pre-calculate.

Caveats dispensed then, let's start with the formal language for the obvious things you notice about Rubik's Cube immediately.

The Basics

This is what a cube looks like when you take it apart:

A disassembled Rubik's cube showing corners, edges, centres and the core mechanism

What to notice here is that the core is fixed so that the centre pieces of each face can never change position.
That is, white is always opposite yellow, blue is always opposite green, and orange always opposite red.
The moveable pieces (corners and edges) we call 'Cubies'.
Corner cubies have 3 colours, and edge cubies have 2 colours.

Orientation

Holding a Rubik's cube showing front and bottom orientation Orientation chosen here: White Up, Green Front (not my cup of tea). When holding the cube you should start by choosing a 'front' and 'bottom' colour.
Everything that follows from here requires that you don't ever change the orientation of the cube during a solve.
Whichever colours you choose for front and bottom should stay the same all the way through the solving process (and probably your whole life)
My preferred orientation is the white centre square at the bottom and the blue centre square at the front (facing towards me)
Your mileage may vary, but because of the way the community works you'll almost always end up going with white at the top or bottom.

Then there are 6 operations (moves) you can perform on a Rubik's cube:

When we say clockwise and anti-clockwise (counter-clockwise) we mean: "as you're looking at that face directly"
This makes a difference for the D an B faces, you'll have to think hard about what clockwise is for the back face initially.
But imagine yourself stepping around behind the cube and looking at the back face.

Other moves which are commonly used

There are also some 'syntactic sugar' moves involving the 'middle' slices.
By which I mean, if you do R and L', the result is the same as moving the centre slice between the L and R faces clockwise (when looking from the left)
So instead of saying "R,L'" we can just say M


There are other ones which deal with turning 'two slices at the same time' (lower case letters), and changing orientation (x, y and z).
But these are not used very often in online listings of common algorithms

NOTE: 'Moves' (UDLRBF) are called 'Generators' in Maths speak

Cubie Names

Rubik's Cube is about moving the 'pieces' of the cube around. It makes sense then to give the cubies a name.
Or more precisely the location where a cubie can be.
These names are usually given as:

This is usually called 'Reid Notation'
Sometimes you'll see these letters in a slightly different order, but you'll be able to work out what it means.
These are the 'holes' where the cubies can go.
The actual cubies can be named as follows (imagine a solved cube):

Armed with this then we can say things like: "yeah the WG edge went to BR"

The Secret

Aside: It is for this reason

To solve a cube you only need to know this:
If you repeat any algorithm (sequence of moves) enough times you'll end up back where you started.

It's a consequence of Lagrange's theorem, which I don't pretend to understand properly
Also, if you run an algorithm and then run it backwards, you'll end up where you started obviously.
Eg, if I do F, U, then do U', F' I'm back where I started.
Why this is important (repetition returns to where you started and moves can be undone) is where the rabbit hole really begins

Some algorithms affect only a small number cubies leaving the rest untouched.
The art of solving a Rubik's cube is finding a set of such algorithms that between them can fix every situation you encounter.
This is to say for example :
R U R' U R U² R' (known to cubers as the "Sune" or "Little Fish" algorithm)
Affects only cubies on the 'U' slice, with an interesting rotating effect

You can see this in action using the analyser at the bottom of this page (just click the analyse button)
This means that you can solve the bottom two layers and still use this algorithm safely without messing up the work you've already done.

You can find such algorithms yourself:
Start with a solved cube and invent a short algorithm (say R U D F).
Run the algorithm once and notice which cubies have been altered, and not altered.
Then just keep repeating it to get back to where you started.
Eventually (maybe after 10 years) you'll have found a full set of such useful algorithms.
The rest of the page discusses how the full set of cube solving algorithms we use today was actually found, saving you ten years of grinding.

The Maths

Mathematicians relevant to Rubik's cube
Some relevant mathematicians

Rubik's cube fascinated mathematicians because it was an ideal test case for a branch of mathematics named 'Abstract Algebra' (just 'Algebra' to actual mathematicians)
I'm not going to walk through the basics of Group Theory or Algebra because we'll be here all year. But I'll just give you this:
When you add two whole numbers, the result is always another whole number (2+2=4, 3+(-2)=1 etc.).
In Math's speak: "The integers form a group under addition" (There are other rules we'll discuss later: Associativity, Identity, Inverses).

And so it is with Rubik's cube... No matter which face of a cube you twist you still end up with a rubiks cube.

The G Group

There are two ways you can think about the possible configuration of an RC.

  1. Starting from a solved cube, the states you can put it in by turning the faces one way or another
  2. The states you can put it in by taking it apart and putting it back together

These two things are different because it's possible to put corner and edge pieces in 'backwards' such that the cube can never be solved.
To use the maths parlance, cube pieces have a 'parity'.
Using the disassemble and reassemble method there are 86,504,006,548,979,712,000 possible configurations of the cube.
To put that into perspective that's a thousand or so more than there have been seconds since the big bang.

How do we know that? Well it's pretty simple:


Multiplying those together gives us the "supergroup" (G_Super) — all mathematically possible arrangements, including ones you could only reach by disassembling the cube:
S₈ × S₁₂ × ℤ₃⁷ × ℤ₂¹¹ = 40,320 × 479,001,600 × 2,187 × 2,048 = 86,504,006,548,979,712,000 ≈ 8.65 × 10¹⁹

But as mentioned only half of them are achievable when using legal moves on a solved cube.
86,504,006,548,979,712,000 ÷ 2 = 43,252,003,274,489,856,000 ≈ 4.33 × 10¹⁹

We can actually write the definition of G (the legal group) as :
G = { (σ_c, σ_e, o_c, o_e) ∈ S₈ × S₁₂ × ℤ₃⁷ × ℤ₂¹¹ | sgn(σ_c) = sgn(σ_e) }
But let's just leave that there!

So we know that we can define a rubiks cube mathematically with:
"Rubik's Cube forms a finite group under Rotation (LRFBUD)"
So what? Well this is where the 'algebra' part comes in. Because we can formally define the cube as a group, we can do algebra on it.

Algebra

Elements

Let's start with elements.
This is where a "cuber's" notion of the cube begins to diverge from the mathematicians view.
As mentioned earlier the cube can be in any one of 43 Quintillion configurations.
That is, the G Group has 43 Quintillion 'elements'.
Each element can be arrived at by one or more 'words' or algorithms (sequence of moves).
So, an 'element' is BOTH a cube state, and whichever sequences of moves arrive at that element (that specific cube state).

But an element is something else (the holy trinity of the G element)

Holding the cube, there is for example the front left edge (lets call it the FL edge).
There's also the Up, Back, Left corner (ULB say) for example. There are 20 such 'positions' that edges and corners can be in.
That is there are 8 possible corner positions, and 12 possible edge positions.
Lets now describe a cube 'state' like this for example:


All other 'cubies' remain as they were.

Don't forget also that a cubie can have an orientation. So for example an edge piece can be in one of two orientations, and a corner piece, three.
So perhaps we'd write our cube 'state' more like this:


All other 'cubies' remain as they were in the same positions with the same orientations.

An 'element' describes this exact set of 'cubie' movements and orientations, the state the cube arrives in after those rearrangements from solved, and any set of moves that can achieve that final 'state'.

That is, any of those ways of looking at what an element of G is, is correct. It just depends on how you're trying to think of an 'element' (for what purpose).

One of the other 'axioms' a group must obey is that it must have an 'identity' element.
For example in the group of integers under addition, zero is the 'identity' element because zero added to any integer returns the same integer.
In our G Group under 'rotation' then, the identity is 'no moves'. More specifically the identity element of G, is the solved state of the cube.
My cube is in some particular state, and I do nothing to it, it stays in that particular state.

The Order Property

We said at the top that if you repeat any sequence of moves (say the 'sexy algorithm', R U R' U') enough times you'll end up where you started.
The same is true if you think in terms of cubie movements. Take our earlier example:

Apply that rearrangement enough times and every piece cycles back to where it started — the cube returns to the identity.
In this case, you apply that set of cubie movements 3 times to return to the start.
Whether you think of it as repeating an algorithm or reapplying a cubie rearrangement the result is the same. The number of repetitions required is called the element's 'Order'. The sexy algorithm for example, has order 6.
The highest order of any element of G is 1260 FYI.

Depth

You may know that the cube can be solved from any possible state (element) in a maximum of 20 moves.
This is known as "God's number" because 20 move solves are generally unintelligible to a human (most human solves take around 40 moves at least)
Obviously some solves require far fewer moves. (imagine a cube whose scramble was just "R'" for example. The solve is just 'R').

Aside: It is for this reason that competition scrambles are usually about 20 moves.
A scramble algorithm generates a genuinely random legal cube state — it knows all possible cubie positions and orientations, respects parity, and chooses at random.
It then finds a move sequence that produces that state from solved. Since most random states have a depth of 17–18, the resulting scrambles tend to be around 20 moves long.

That is, the minimum number of moves it would take God to solve the cube from any given element, is called its 'Depth'.

Subgroups

A subgroup is what you think it is. It's any subset of the whole group for which the axioms of 'groups' still apply.

The Secret, Redux

The secret to solving Rubik's cube (from a maths perspective) is to move from G, into ever smaller subgroups (Let's call them G → G₁ → G₂ → G₃ etc.) until eventually you reach the trivial subgroup (the identity element, the solved cube.)

All very well you say, but how on earth do I reduce the size of a group?

Group size reduction strategies

The whole group 'G' deals with every cubie of the group and every possible 'generator' (move, such as F, D, U etc.)
Obvious ways to reduce a group are then to restrict the cubies a subgroup deals with or the generators (moves) it's allowed to use.

Others include reducing groups by symmetry, using coset decomposition to partition a group into manageable equivalence classes, and exploiting conjugacy to treat configurations that are essentially the same move sequence applied in a different orientation.
Scary stuff, but you can these because I'm not going to discuss them.

Reducing subgroups by limiting the allowed moves

One such strategy is Thistlethwaite's subgroups:
- G₀ = G = ⟨L, R, F, B, U, D⟩ — all moves allowed - G₁ = ⟨L, R, F, B, U², D²⟩ — U and D restricted to half-turns only (no quarter turns allowed) - G₂ = ⟨L, R, F², B², U², D²⟩ — F and B also restricted to half-turns - G₃ = ⟨L², R², F², B², U², D²⟩ — all faces restricted to half-turns - G₄ = {identity} — solved Each subgroup is defined purely by which generators are permitted.
The solving strategy is then: at each phase, find a sequence of moves (using the current phase's generators) that puts the cube into a state where the next phase's restricted generators are sufficient to continue.

From a human perspective this is not possible, it's a computational strategy requiring lookup tables and search algorithms etc.

Another such computational strategy is Kociemba's subgroups (the one widely used in computational solvers today):
- G₀ = G = ⟨L, R, F, B, U, D⟩ — all moves - G₁ = ⟨L, R, F², B², U², D²⟩ — F, B, U, D restricted to half-turns - G₂ = {identity} — solved

As you can see, this is just a cut down version of Thistlethwaite's subgroups.
It does mean moving between subgroups requires a lot more processing power, but modern computers are easily up to the task.

Reducing subgroups by limiting the affected area

Obviously you can first solve 'part' of the cube (say the bottom face), then dispense with any elements of G that 'mess up' the bottom face.
And in fact this is how human solving works, and in fact how the algorithms used in human solving were found.

- G₀ = G — the full group, scrambled cube - G₁ = {states where the cross is solved} — 4 bottom edges correctly placed and oriented - G₂ = {states where cross + F2L are solved} — all first two layers complete (4 bottom edges, 4 corner-edge pairs) - G₃ = {states where cross + F2L + OLL is solved} — last layer pieces all oriented correctly (yellow face complete, but pieces may be in wrong positions) - G₄ = {identity} — solved

CFOP - Friedrich

TODO: Insert picture of Jessica Fridrich

Algorithm Analyser

Type any algorithm below to see exactly which cubies move where, how they're twisted or flipped, and the cycle structure. The cube starts solved with yellow up and blue front.

Cube State

Reid Notation

Element

Summary

Corners

PositionCubieTwist

Edges

PositionCubieFlipped