You can solve the cube – with commutators!

After a couple years of living out of suitcases, we recently sold our house in Pasadena, and bought a new one in Hyde Park. All our junk was shipped to us, and the boxes we didn’t feel like unpacking are all sitting around in the attic, where the kids have been spending a lot of time this summer. Every so often they root through some box and uncover some archaeological treasure; so it was that I found Lisa and Anna the other day, mucking around with a Rubik’s cube. They had persisted with it, and even managed to get the first layer done.

I remember seeing my first cube some time in early 1980; my Dad brought one home from work. He said I could have a play with it if I was careful not to scramble it (of course, I scrambled it). After a couple of hours of frustration trying to restore the initial state, I gave up and went to bed. In the morning the cube had been solved – I remember being pretty impressed with Dad for this (later he admitted that he had just taken the pieces out of their sockets). Within a year, Rubik’s cube fever had taken over – my Mum bought me a little book explaining how to solve the cube, and I memorized a small list of moves. I remember taking part in an “under 10” cube-solving competition; in the heat of the moment, I panicked and got stuck with only two layers done (since there were only two competitors, I came second anyway, and won a prize: a vinyl single of the Barron Knights performing “Mr. Rubik”). The solution in the book was a procedure for completing the cube layer by layer, by judiciously applying in order some sequence of operations, each of which had a precise effect on only a small number of cubelets, leaving the others untouched. In retrospect I find it a bit surprising – in view of how much effort I put into memorizing sequences, reproducing patterns (from the book), and trying to improve my speed – that I never had the curiosity to wonder how someone had come up with this list of “magic” operations in the first place. At the time it seemed a baffling mystery, and I wouldn’t have known where to get started to come up with such moves on my own. So the appearance of my kids playing with a cube 33 years later is the perfect opportunity for me to go back and work out a solution from first principles.

The one useful item I remember from that book was the notation for the cube operations; if we orient the cube in a particular way, and label the faces as up, down, front, back, left, right (in the obvious way), then an anticlockwise twist of one of these faces is denoted by a lower case letter u,d,f,b,l,r and a clockwise twist by the corresponding upper case letter U,D,F,B,L,R. Thus a sequence of moves – and its effect on a cube (in solved initial state) is illustrated in the following figure:

There is nothing special about the sequence RuRLdBBFRulBDD; the idea is just to observe how scrambled the cube can become with the application of a very small number of moves.

The first step of the solution is to “build a layer” – i.e. to get all the cubelets with some given color into the correct position and orientation. This can be done quite easily – first get the “edge cubelets” (those which have two free faces) into place, then the “vertex cubelets”. I think this really is something that can be achieved just by a bit of mucking about, and if you have never played with a cube before, I encourage you to get one, play around with it, and try to build a layer, just to see how easy it is (if a physical cube is hard to come by, you can always play around with the .eps code that generated these figures; see the end of the post). In fact, exactly the same techniques will let you put any four edge cubelets and any four vertex cubelets together in a face, in any orientation, providing you don’t care about the effect on the rest of the cube. This latter observation may not seem particularly useful at this stage, but in fact it is the key to a complete solution; for the sake of notation, let’s refer to this step as setting up a face.

Now, having built the first layer, the next step is to build the second layer. There are four edge cubelets that need to be positioned in the second layer; if the first layer is intact, these cubelets are either in the second layer but in the wrong position or orientation, or they are in the third layer. So it suffices to work out how to swap a cubelet from the second layer with one in the third layer – without disturbing the rest of the first or second layers, of course. Well, as an intermediate step, suppose we can swap a cubelet from the second layer with one in the third layer, putting no restrictions on what the effect is on the first or second layer. That’s easy – it’s just the operation of setting up a face. So we can find some sequence of moves that does what we want – call it s – and then survey the result. After performing s, the two edge cubelets that we want to interchange are both in the third layer, and everything else in the third layer was there before performing s. So let’s just twist the third layer (by some power of the “U” move) and replace the cubelet from the second layer with the cubelet from the third layer we want to replace it with. Now here’s the trick: follow that by performing S – the inverse of the operation s. The net result is the operation sUS – a conjugate of U. What is its effect? Well, the operation U itself just permutes the eight cubelets in the top layer (nine including the center, which is fixed of course). So any conjugate of U will also permute just eight cubelets. Which eight? Well, the eight which are in the third layer after performing s – i.e. 7 cubelets from the initial third layer, and the cubelet from the second layer we want to swap. Thus sUS has the effect of swapping one cubelet between the second and third layer, while leaving the remainder of the second and first layers intact, which is exactly what we want. Some experimentation gives a short recipe for an operation of the form s; the result is illustrated in the next figure:

The third layer can be solved by a similar principle. Consider a setting up a face operation s which takes the cubelets in the third layer and scrambles them in a precise way – e.g. by interchanging two edge or vertex cubelets, or changing the orientation of one edge or vertex cubelet. This has some (unpredictable) effect on the first two layers, mucking them up somehow. But the commutator of s and U – i.e. the operation sUSu – will unscramble the first two layers, putting them back as they were, since the support of U is the third layer, and therefore U commutes with any permutation of the first two layers. The effect on the third layer is relatively easy to predict; in the cases described above, it will cyclically permute three edge or vertex cubelets, or change the orientation of two edge or vertex cubelets respectively. These four moves, used in concert, can unscramble the third layer; here’s an explicit example (in this example, one of the moves on edge cubelets affects the vertex cubelets, so the edge cubelets should be put into the correct location and orientation first, and then the vertex cubelets):

There is no claim that these operations are “optimal”; they’re the first thing I came up with when I worked this out last night. Note that these operations do not allow you to set the third face up in an arbitrary way while keeping the first two faces fixed; this is because the allowable operations of the Rubik’s cube do not generate the full group of permutations of the oriented cubelets (even conditioned on taking vertex cubelets to vertex cubelets and edge cubelets to edge cubelets). I leave it as an exercise in finite group theory to show that the operations described above allow one to unscramble the cube from any configuration in which it can be unscrambled by legal moves.

That’s it! That’s the whole solution. Similar ideas make it easy to solve variations on the cube (e.g. 4x4x4, cubelets with pictures on the faces, tetrahedra, etc.). And it was quite gratifying to see Anna and Lisa so excited to discover the solved cube this morning (and to know that I hadn’t cheated!)

If you want to play with the .eps code that generated these figures, I’ve attached it at the end (yes, I know it’s a hack):


%!PS-Adobe-2.0 EPSF-2.0
%%BoundingBox: 0 0 300 300
gsave
100 100 scale
1 100 div setlinewidth
1 setlinejoin
1.5 1.5 translate
/Helvetica findfont
0.1 scalefont
setfont
/square{6 dict begin
/c exch def
/k exch def
/j exch def
/i exch def
/xc i 2 mul 2 sub j 3 div add def
/yc k 3 div def
c 0 eq {
0 0 0.7 setrgbcolor
} {
c 1 eq {
0.8 0 0 setrgbcolor
} {
c 2 eq {
1 1 0 setrgbcolor
} {
c 3 eq {
0.9 0.9 0.9 setrgbcolor
} {
c 4 eq {
1 0.6 0.2 setrgbcolor
} {
0 0.5 0 setrgbcolor
} ifelse
} ifelse
} ifelse
} ifelse
} ifelse
i 0 eq {
% i=0
newpath
0 0.28867513459481 j mul add -1 0.166666666666 j mul add 0.33333333333333 k mul add moveto
0.28867513459481 0.28867513459481 j mul add -0.8333333333333 0.166666666666 j mul add 0.33333333333333 k mul add lineto
0.28867513459481 0.28867513459481 j mul add -0.5 0.166666666666 j mul add 0.33333333333333 k mul add lineto
0 0.28867513459481 j mul add -0.66666666666 0.166666666666 j mul add 0.33333333333333 k mul add lineto
closepath
fill
stroke
} {
i 1 eq {
% i=1
newpath
0 0.28867513459481 j mul add 0.28867513459481 k mul sub 0 0.166666666666 j mul add 0.166666666666 k mul add moveto
0.28867513459481 0.28867513459481 j mul add 0.28867513459481 k mul sub 0.166666666666 0.166666666666 j mul add 0.166666666666 k mul add lineto
0 0.28867513459481 j mul add 0.28867513459481 k mul sub 0.3333333333 0.166666666666 j mul add 0.166666666666 k mul add lineto
-0.28867513459481 0.28867513459481 j mul add 0.28867513459481 k mul sub 0.166666666666 0.166666666666 j mul add 0.166666666666 k mul add lineto
closepath
fill
stroke
} {
i 2 eq {
% i=2
newpath
-0.86602540378444 0.28867513459481 j mul add -0.5 0.166666666666 j mul sub 0.33333333333 k mul add moveto
-0.86602540378444 0.28867513459481 add 0.28867513459481 j mul add -0.5 0.166666666666 sub 0.166666666666 j mul sub 0.33333333333333 k mul add lineto
-0.86602540378444 0.28867513459481 add 0.28867513459481 j mul add -0.5 0.166666666666 add 0.166666666666 j mul sub 0.33333333333333 k mul add lineto
-0.86602540378444 0.28867513459481 j mul add -0.5 0.333333333333 add 0.166666666666 j mul sub 0.33333333333333 k mul add lineto
closepath
fill
stroke
} {
i 3 eq {
% i=3
gsave
1 1 translate
0.4 0.4 scale
newpath
-0.86602540378444 0.28867513459481 j mul add 0.5 0.16666666666666 j mul add 0.333333333333 k mul sub moveto
-0.86602540378444 0.28867513459481 add 0.28867513459481 j mul add 0.5 0.16666666666666 add 0.16666666666666 j mul add 0.333333333333 k mul sub lineto
-0.86602540378444 0.28867513459481 add 0.28867513459481 j mul add 0.5 0.16666666666666 sub 0.16666666666666 j mul add 0.333333333333 k mul sub lineto
-0.86602540378444 0.28867513459481 j mul add 0.5 0.33333333333333 sub 0.16666666666666 j mul add 0.333333333333 k mul sub lineto
closepath
fill
stroke
grestore
} {
i 4 eq {
% i=4
gsave
1 1 translate
0.4 0.4 scale
newpath
-0.86602540378444 0.28867513459481 j mul add 0.28867513459481 k mul add -0.5 0.16666666666666 j mul add 0.16666666666666 k mul sub moveto
-0.86602540378444 0.28867513459481 add 0.28867513459481 j mul add 0.28867513459481 k mul add -0.5 0.16666666666666 add 0.16666666666666 j mul add 0.16666666666666 k mul sub lineto
-0.86602540378444 0.28867513459481 2 mul add 0.28867513459481 j mul add 0.28867513459481 k mul add -0.5 0.16666666666666 j mul add 0.16666666666666 k mul sub lineto
-0.86602540378444 0.28867513459481 add 0.28867513459481 j mul add 0.28867513459481 k mul add -0.5 0.16666666666666 sub 0.16666666666666 j mul add 0.16666666666666 k mul sub lineto
closepath
fill
stroke
grestore
} {
% i=5
gsave
1 1 translate
0.4 0.4 scale
newpath
0 0.28867513459481 j mul add 0 0.16666666666666 j mul sub 0.333333333333 k mul add moveto
0 0.28867513459481 add 0.28867513459481 j mul add 0 0.16666666666666 sub 0.16666666666666 j mul sub 0.333333333333 k mul add lineto
0 0.28867513459481 add 0.28867513459481 j mul add 0 0.16666666666666 add 0.16666666666666 j mul sub 0.333333333333 k mul add lineto
0 0.28867513459481 j mul add 0 0.33333333333333 add 0.16666666666666 j mul sub 0.333333333333 k mul add lineto
closepath
fill
stroke
grestore
} ifelse
} ifelse
} ifelse
} ifelse
} ifelse
end} def
/display{5 dict begin
/V exch def % vector of 54 colors
0 1 5{
/i exch def
0 1 2{
/j exch def
0 1 2{
/k exch def
/n i 9 mul j 3 mul add k add def
i j k V n get square
} for
} for
} for
gsave
0 0 0 setrgbcolor
0 1 1{
gsave
0 1 2{
gsave
0 1 3{
newpath
0 0 moveto
0 -1 lineto
stroke
0.28867513459481 0.166666666666 translate
} for
grestore
gsave
0 1 2{
-0.28867513459481 0.166666666666 translate
newpath
0 0 moveto
0 -1 lineto
stroke
} for
grestore
120 rotate
} for
grestore
1 1 translate
0.4 0.4 scale
180 rotate
} for
grestore
end} def
/U{2 dict begin
/V exch def
/i V 2 get def
V 2 V 53 get put
V 53 V 33 get put
V 33 V 20 get put
V 20 i put
/i V 5 get def
V 5 V 50 get put
V 50 V 30 get put
V 30 V 23 get put
V 23 i put
/i V 8 get def
V 8 V 47 get put
V 47 V 27 get put
V 27 V 26 get put
V 26 i put
/i V 9 get def
V 9 V 15 get put
V 15 V 17 get put
V 17 V 11 get put
V 11 i put
/i V 12 get def
V 12 V 16 get put
V 16 V 14 get put
V 14 V 10 get put
V 10 i put
V
end} def
/F{2 dict begin
/V exch def
/i V 9 get def
V 9 V 27 get put
V 27 V 36 get put
V 36 V 0 get put
V 0 i put
/i V 10 get def
V 10 V 28 get put
V 28 V 37 get put
V 37 V 1 get put
V 1 i put
/i V 11 get def
V 11 V 29 get put
V 29 V 38 get put
V 38 V 2 get put
V 2 i put
/i V 26 get def
V 26 V 20 get put
V 20 V 18 get put
V 18 V 24 get put
V 24 i put
/i V 23 get def
V 23 V 19 get put
V 19 V 21 get put
V 21 V 25 get put
V 25 i put
V
end} def
/R{2 dict begin
/V exch def
/i V 9 get def
V 9 V 24 get put
V 24 V 44 get put
V 44 V 53 get put
V 53 i put
/i V 12 get def
V 12 V 25 get put
V 25 V 41 get put
V 41 V 52 get put
V 52 i put
/i V 15 get def
V 15 V 26 get put
V 26 V 38 get put
V 38 V 51 get put
V 51 i put
/i V 2 get def
V 2 V 0 get put
V 0 V 6 get put
V 6 V 8 get put
V 8 i put
/i V 5 get def
V 5 V 1 get put
V 1 V 3 get put
V 3 V 7 get put
V 7 i put
V
end} def
/D{2 dict begin
/V exch def
/i V 0 get def
V 0 V 18 get put
V 18 V 35 get put
V 35 V 51 get put
V 51 i put
/i V 3 get def
V 3 V 21 get put
V 21 V 32 get put
V 32 V 48 get put
V 48 i put
/i V 6 get def
V 6 V 24 get put
V 24 V 29 get put
V 29 V 45 get put
V 45 i put
/i V 37 get def
V 37 V 39 get put
V 39 V 43 get put
V 43 V 41 get put
V 41 i put
/i V 36 get def
V 36 V 42 get put
V 42 V 44 get put
V 44 V 38 get put
V 38 i put
V
end} def
/B{2 dict begin
/V exch def
/i V 6 get def
V 6 V 42 get put
V 42 V 33 get put
V 33 V 15 get put
V 15 i put
/i V 7 get def
V 7 V 43 get put
V 43 V 34 get put
V 34 V 16 get put
V 16 i put
/i V 8 get def
V 8 V 44 get put
V 44 V 35 get put
V 35 V 17 get put
V 17 i put
/i V 45 get def
V 45 V 47 get put
V 47 V 53 get put
V 53 V 51 get put
V 51 i put
/i V 46 get def
V 46 V 50 get put
V 50 V 52 get put
V 52 V 48 get put
V 48 i put
V
end} def
/L{2 dict begin
/V exch def
/i V 11 get def
V 11 V 47 get put
V 47 V 42 get put
V 42 V 18 get put
V 18 i put
/i V 14 get def
V 14 V 46 get put
V 46 V 39 get put
V 39 V 19 get put
V 19 i put
/i V 17 get def
V 17 V 45 get put
V 45 V 36 get put
V 36 V 20 get put
V 20 i put
/i V 27 get def
V 27 V 33 get put
V 33 V 35 get put
V 35 V 29 get put
V 29 i put
/i V 28 get def
V 28 V 30 get put
V 30 V 34 get put
V 34 V 32 get put
V 32 i put
V
end} def
/V [0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5] def
V R U U U R L D D D B B F R U U U L L L B D D display
0 setgray
newpath
-0.65 -1.2 moveto
( R u R L d B B F R u l B D D ) show
stroke
grestore
%eof