Tuesday, September 25, 2012

Solving the Rubik's Cube, Part 2: Exploration

Now that we have a better idea what we're dealing with, we can start rotating things to see what happens.

Fortunately, these cubes come solved. When working with a solved cube, it's much more obvious what is the effect of any transformation, since you can immediately tell (roughly) where each block came from. In order to take advantage of the solved state as long as possible, we start by only making small excursions of 4-8 operations.

Before we can talk about these operations, we need to define a language for describing operations and positions on the cube. We'll start by naming the six directions with their unique first letters: Front, Back, Up, Down, Left, and Right. Each block can be described by three coordinates, using capitalization as follows: we write 'F' for front-most, 'f' for front-middle, 'b' for back-middle, and 'B' for backmost; and likewise for the other two axes. Thus, the front-top-left corner cube will be called 'FUL', the edge cube directly beneath it is 'FuL', and the face cube to the right of it is 'Ful'. Continuing diagonally right and down the same face we have 'Fdr' and finally the opposite corner 'FDR'. We always use the same order F/f/b/B, followed by U/u/d/D, followed by L/l/r/R, so that each block has a single unique name. Note that corner blocks are all caps, edge blocks are two caps and a lowercase, and face blocks are two lowercase and one capital. A block with all three lowercase is impossible as it would be on the inside of the cube.

We now name the elementary rotations by the direction of rotation, subscripted by which layer is turned. Thus, turning the top-most layer to the right is RU. Turning the next lower layer to the left is Lu. Turning the right-most layer down is DR and turning the middle-left layer up is Ul. To name the final axis, we use the right-hand-rule: a counter-clockwise rotation of the front layer is FF since this is a right-hand rotation through the F-axis. A clockwise rotation of the middle-front layer is Bf. We could name the other four rotations by their axis, but I find the consistency to not be worth the increased confusion.

Now that we have names, what sort of explorations can we do? Our goal now is to build up a catalog of simple (and hopefully easy-to-remember) operations that make small changes to the cube that are easy to understand and reason about. For instance, a single rotation Dr affects 12 on four separate faces, which is a bit unwieldy. If we follow it up with Rd we've now affected 22 blocks, touching all the faces: even worse. But if we continue with Ur and then Ld, we arrive mostly back to where we started, but with six face blocks cycled a bit. If we repeat this series of four rotations three more times, we arrive back at a completely-solved cube. Another example is DrRDUrLD. [Note that I write compositions from left to right, which is unconventional from a mathematical point of view—i.e. if you wrote these as functions f and g operating on a state s then one might expect (fg)(s) to mean f(g(s)); but I find this more difficult to read and this leads to more errors in executing operations on an actual cube.] This operation also affects six blocks, but must be repeated more times to return to the initial state.

We've seen 6×4=24 named operations, to which we can add 6 more full-cube rotations: OF, OB, OU, OD, OL, and OR, again using the right-hand rule to determine rotation direction. Note that these are effectively just relabelings: OFUrOB is equivalent to just Ld. In this way, one might consider them a sort of orthogonal (or unitary, for the physicists) transformation.

This is a small sampling of short excursions. In the next installment, we'll look at many more, and discuss some heuristics of how we come up with possible operations and how to represent their effects using cycle notation.


Unknown said...

I find this article quite interesting, and am wondering where are the next installments?
It would be nice to see the follow-ups, thanks.

Steve said...

Wow, it's been 4 years. I may someday get around to finishing this, but sadly I got very busy with a lot of other stuff, so it's not all that likely. So for now, this is all that exists.