### Solving Rubik's Cube

A few weeks ago I went on a recruiting thingie at the Cambridge Computer Lab. As well as trying to recruit grads, it's a chance to grab freebies from other stands. I got a nice Rubik's Cube, which gave me a bit of a flashback.

When I was small, I got a Rubik's Cube, but never solved it. Fun, but frustrating. When the Rubik's Magic came out, I sidestepped the whole puzzle element, and got it with a book solving it. I think I missed the point a bit there, but it was a good fun toy. When the Rubik's Clock came out, I finally solved one. Got it Christmas Day, solved it Boxing Day, my family thought it wasn't good value for money, but I rather enjoyed it. A couple of years later, I got a little book on solving the Rubik's Cube, but didn't actually work out how to solve it myself. Ho hum.

So, this time round I thought I'd solve it properly. My plan was to grab a few basic sequences, and then build it up into a full solving sequence. First, a bit of notation. The front and back faces are F and B. L and R for left and right, and U and D are the top and bottom. Edges pieces can be specified with two letters (e.g. UR), and corners with three (e.g. URF). I'll write a particular face rotation with either a positive sign (e.g. +U) for that face being rotated clockwise, or minus for anticlockwise. I'll use '3X' to mean repeating the sequence 'X' 3 times.

So, after a few simple experiments, I find the sequence 3(+L+L+U+U) swaps FU and BU, and FL and BL. The other sequence I used was based on explicitly trying to shuffle some of the squares around. The sequence is +L+F+F-R+F+F-L+F+R-F, and what it does to the top is... complex. We'll call this sequence 'X'.

It's easy enough to get one face sorted, so that one third is right. Put that face on D and then line up the centres of the non-U faces to match the colours on the lower edge. Then all you need to do to get the middle sorted is to fix the edges in the middle layer. You can do this by arranging it so that the ones you want to swap are at FR and UL, and then do +L+U 3(+U+U+F+F) -U-L. Once you've done that for all the middle edges, it's only the top to go!

We can now use this 'X' sequence to tidy up the top. X will shuffle around various edges and corners, and change which face of them faces where, but main thing to note is that URB stays where it is (turning in place), while the other corners rotate round. So, by putting the appropriate top corner into URB and applying X, you should be able to get the corners into place for the appropriate colours. However, they won't yet be facing the right way up.

Applying X 3 times shuffles puts the corners back where they started, but facing different ways up. More specifically, URB is identical to how it was before, but the other three corners are turned clockwise on the spot. By repeatedly carefully choosing the corner to be URB, and then applying 3X, you'll now have everything complete but the top edges. The top edges can now be completed by variations on the 3(+L+L+U+U) sequence. If you want to swap two pairs of faces, it then becomes quite simple: Find a short sequence which places those pairs you want to swap into FU/BU and FL/BL, apply the swap sequence, and then undo your original sequence by running it backwards (unturning faces in the reverse order). My group theory is more than a little rusty, but the operations you can create this way are the conjugates of our original swap operation. This is the technique we used to fix up the middle-layer edges.

This will do a certain amount of edge-swapping, but we can end up with situations where we want to rotate around three edges, and the swap operation doesn't make this look easy. Can we do it? We can't do it by just swapping top edges, but we can temporarily untidy the middle. Let's say we want to cycle UL, UB and UF. We'll choose two more 'victim' edges, whose roles are to be swapped at appropriate times, but end up where they started. These will be FL and FR. Then we arrange a pair of those conjugate-based swaps, to achieve the cycle. In the following table, each new row represents two sets of edges being swapped around. The swapped elements are in bold:

 UB UL UF FL FR UL UB UF FR FL UL UF UB FL FR

At the end, we've cycled those three pieces around. While I haven't proven it, this appeared to be the final piece I needed, and I've been able to solve the cube several times using the above toolkit. It is, however, a very unwieldy toolkit. The sequences chosen are built by incremental construction from smaller sequences, rather than finding the shortest sequence to do the job. The idea was to see how much I could build up starting with only a very small set of 'primitive' operations. If you're interested in solving the cube quickly, the booklet I bought all those years ago, 'Resolving Rubik's Cube' by Jon Millington, does the job most effectively, although not with much in the way of motivation. There's plenty of fun in finding your own way to solve the cube, though.

Posted 2007-12-10.