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

Reblogged this on riemannian hunger and commented:

This is a super interesting read.

Danny, did you notice that the pre-algebra book I showed you in Portland had a chapter on solving the rubik’s cube, using group theory? :)

If only I’d had that pre-algebra book in 1980 . . .

But can you solve it in 20 moves from any position?

Maybe 50.

Of course, one thing that makes the cube possible to unravel is that the corresponding group G is highly transitive (at least on the tiny cubes which are in the same orbit).

One thing one can do with the Rubix cube (or rather two cubes, in order to get enough stickers) is to make the opposite faces have the same color). It’s not immediately clear whether this 3-color cube might not be *harder* to solve than the original cube, because one might move some combination of blue squares to the top face when, in fact, they have to end up on different faces. In practice, I think that G is transitive enough so that this can’t happen, but I haven’t done the actual computation.

This is a great point. Actually, I think the difficulty you propose can really manifest itself, since (I believe) that any allowable transformation which permutes only vertex cubelets, leaving the edge cubelets fixed (for instance) is an even permutation. So a transformation which interchanges one vertex cubelet for the antipodal one (leaving everything else fixed) is impossible; and if the cube is colored with antipodal symmetry, one might set up the bottom two faces with one “wrong” vertex cubelet on the bottom face, and then be unable to complete the top face.

Of course, in practice one would discover this at the end, with only two vertices in the top face (apparently) out of place; one could exchange one for the antipodal vertex using the move which permutes three vertex cubelets. So: not *much* harder.

Just curious – are your cube-mania memories compatible with mine, or did I just make all this up? or were you too young in 1980-81 to remember?

It’s consistent with what I remember. I seem to remember you coming second in some competition (although I wasn’t there). I also remember a number of cubes which had gone all wobbly because they had been taken apart and put together once too often. I don’t think I played too much with the cubes myself. I guess it was more fun than picking up nails during the RMIT renovation.

Danny,

I think that the following simple fact about the symmetric group makes your use of commutators a bit more transparent. Let g and h be two elements of the symmetric group and let [g,h] be their commutator. When g and h have no common support (that is, they move different elements of the set) it is easy to see that [g,h] = 1. Now suppose that they have a unique element a in their common support. Then their commutator [g,h] is just the three cycle

(a g(a) h(a)). This is as simple an even element as possible (without being

trivial), and gives many of the desired moves on the cube.

Hi Dick – yes, that’s a nice way of putting it. Thanks for the comment!

Is that book Prof.Donald Taylor’s Mastering the Rubik’s Cube ? I have the book, published in 1980, based on conjugates and commutators.

Hi P.S. – no, the book I had was much more elementary. It really just focussed on describing a sequence of moves that could be used to solve the cube, with no discussion of theory at all.

This book also does not have any theory. After perfecting the method proposed in this book for I is now after almost 3 decades that I realize that this solution was based in conjugates and commutators. The first layer is solved intuitively. The second layer is solved through a commutator. After permuting the top layer corners, the beauty of the method proposed by Prof Don Taylor is that it does not matter in what sequence you finish the cube. You may permute the edges, orient the edges or orient the corners in any sequence, as all of them are based on commutators. This may not be an optimal solution for the present day speed cubers but is definitely a more scientific method. There are no lengthy algorithms to be memorized. You just need knowledge of 6-7 conjugates and commutators. See number 6 in Books.

http://www.maths.usyd.edu.au/u/don/details.html#pubs

In fact you might be right! I found an image of the book on google images, and it

doeslook familiar. Thanks very much!