Rubik's cube

I've been playing with the Rubik's cube a lot lately. I enjoyed it when it came out in the 80's, and I'm enjoying it more now that I know a bit of group theory. This webpage has some of the things I figured out. Now that I've written them down I don't have to worry about forgetting them, so maybe I can put the thing away and get some work done.

Notation

A Rubik's cube is made of eight "corner pieces", twelve "edge pieces", and six "center pieces".

I'll use fairly standard notation to describe moves. The six basic clockwise quarter turns are F, B, U, D, L, R. These generate the "Rubik's cube group". A letter followed by a 2 means a 180 degree turn. A letter followed by a prime means a counterclockwise turn.

I'll also use lowercase letters f, b, u, d, l, r to mean turn two layers simultaneously. These are not usually included in the Rubik's cube group because, for example, r is the same as doing L and then turning the entire cube upwards. However it can be useful to think of r and L as different moves in the "oriented Rubik's cube group". This is the group generated by the Rubik's cube group together with the group of twenty-four ways to rotate the entire cube.

The "slice moves" are especially useful elements of the oriented Rubik's cube group. These are moves where you turn a middle layer of the cube. For example, (d D') is the slice move that turns the "equator" to the right.

An "algorithm" is a sequence of moves that has some useful effect. (Confusingly, an "algorithm" can also mean a recipe for solving the cube, which may itself contain several algorithms.) If FOO and BAR are algorithms

Simple solution

Here is my solution for the Rubik's cube. It works equally well for any n-by-n cube. It is supposed to be as simple as possible. There are a very small number of algorithms, and it is easy to understand exactly how they work. However I will assume you know some group theory (or can fake it), and that you can figure out some details for yourself.

First let's do the 2-by-2 cube. The solution is all based on the following algorithm.

DROP = R' D2 R

This will "drop" a piece from the top layer. Of course it will also "pick up" a piece to the top layer. It is an involution. You can permute the pieces on the top face by a sequence of DROPs and turns of the top face. For example,

CYCLE = DROP U DROP U DROP U2 DROP

This cycles three of the pieces on the top layer, and leaves all other pieces unchanged. Two things are needed to make this work: there are an even number of DROPs, and the last DROP drops the piece that was picked up by the first DROP.

You can use a conjugate of CYCLE to simultaneously twist and cycle pieces. For example,

CYCLONE = F CYCLE F'

This cycles three pieces in the top layer and twists two of them in opposite directions.

You can combine CYCLE and CYCLONE to twist pieces without permuting them. For example,

TWIST = CYCLONE U CYCLE' U'

This twists two pieces on the top layer, and leaves all other pieces unchanged.

You can use a sequence of conjugates of CYCLE and TWIST to position and orient pieces one at a time. If you get down to just two pieces in the wrong position then you have the wrong parity, since conjugates of CYCLE can only perform even permutations. You can fix the parity by simply turning a face.

For the 3-by-3 cube, you can use all of the above procedures to position and orient corner pieces without moving edge pieces. You can use the same basic idea to position and orient edge pieces without affecting the corner pieces. For example,

Now you can independently position and orient the corner and edge pieces one at a time to solve the 3-by-3 cube.

For the n-by-n cube, instead of just corner and edge pieces, you now have more "orbits" to deal with. For each orbit you can use CYCLE and TWIST similar to the ones we used above for edge pieces, but using the appropriate slice moves. There are a couple of extra complications. First, there is no way to "twist" a piece unless it is in the corner or the exact middle of an edge. If it looks as though you need to twist an edge piece that is not in the center of the edge, then what you actually need to do is move that piece to the other side of the same edge. You can do this with a variant of TWIST. Second, the "parity" issue can be more confusing because you might need to exchange two identical looking pieces.

This algorithm is quadratic in the size of the cube. I don't know if anything is known about growth rates of solutions for n-by-n cubes. In practice it is very slow. The most obvious inefficiency is that TWIST and CYCLE, which are designed to affect only a small number of pieces, are kind of pointless early on when most of the cube is a mess anyway. Once you understand what you're doing, it's easy to make improvements.

The human Thistlethwaite algorithm

When looking for Rubik's cube algorithms on the internet, I stumbled on Ryan Heise's "human Thistlethwaite algorithm". (I actually know the human called Morwen Thistlethwaite, who invented the Thistlethwaite algorithm We are both mathematicians, and specifically knot theorists, so it was a shock to see his name pop up when I was indulging in my extra-curricular "research".)

The Thistlethwaite algorithm began the search for optimal solutions, which try to solve any position in as small a number of moves as possible. Ryan Heise's "human Thistlethwaite" algorithm strikes a balance between being optimal and being easy enough for a human to master without the use of computers or long tables of algorithms. He also takes this further and gives a solution that uses no "mysterious algorithms", meaning that the effect of every sequence of moves should be logically clear.

Some of Heise's algorithms still seemed a little mysterious to me. My algorithm is supposed to be less optimal and less mysterious than Heise's. I'm not sure if it succeeds, but I still think it's fun, so here it goes.

The idea of the Thistlethwaite algorithm is to progress step by step into smaller and smaller subgroups of the Rubik's cube group. The sequence of subgroups is as follows.

For example, the first step is to get the cube into a position where you know you will never again have to turn the front or back face except by half turns. More recent improvements on the Thistlethwaite algorithm use fewer subgroups. My solution uses more subgroups: Here, SS is the "slice square" group SS = < (r2 R2), (u2 U2), (f2 F2) >, and A is the "approximate cube group". For any position of the cube, a sticker is "approximately the right color" if it is the color of either that face or the opposite face. The cube is in A if and only if every sticker is approximately the right color.

The steps in my solution are as follows:

For the first five steps, you should pretend you can't tell the difference between the colors on opposite faces of the cube. It helps that on a standard cube, opposite faces have similar looking colors. Once you get into the approximate cube group, it kind of looks like it would be solved if you were slightly color blind.

The squares group preserves the "approximately solved" appearance of the cube, but it might not be enough to solve it. Here are two mysterious algorithms that belong to A, but not the squares group.

FOURCYCLE = (D' f' F' D2 r R) U (R' r' D2 F f D)

TWOTWO = F (R' D R D')^3 F'.

Then there's the mirror image of TWOTWO.

OWTOWT = F' (L D' L' D)^3 F.

If the cube is approximately solved then you can hold it in some orientation and do one of the above three algorithms to get it in the squares group.

The difficulty is figuring out which orientation to hold the cube and which of the three algorithms to apply. You can completely ignore the center and edge pieces at this point. That cuts down on the number of patterns, but it's still difficult. One method is to try to solve the corners using 180 degree turns, and then recognise a few positions where you need to apply one of the above three algorithms.

The rest of the solution is much easier, and doesn't really need any memorized algorithms. See Ryan Heise for more algorithms and more help. See also Jaap's posting of Thistlethwaite's original algorithm.