Rubik's Cube 1-Guest Post by Matt Tai

My friend Matt Tai taught me to solve the Rubik's cube. So I asked him to give a series of guest posts on the subject. He threatened to send me a copy of  Henry VIII instead of that post. As the version of Henry VIII he sent me was the play by  William Shakespeare and not the genome sequence of the British King. I managed to convvince him to give us a post on the Rubik's cube today. Hopefully (though it's unlikely) he'll give us the genome sequence next time.

Stuff Matt actually wrote below

The Rubik's cube, invented by Erno Rubik, is a puzzle that has become a cultural icon, a puzzle whose difficulty is widely acknowledged.

The idea of the puzzle is not terribly complex. The cube is subdivided into 27 smaller "cubies", arranged 3 by 3 by 3. The basic action is to grab a 3 x 3 square of these cubies that make up a face of the larger cube, and twist the square around the center cubie; you can twist it a quarter of the way around, halfway around, or three-quarters of the way around. Twisting it four quarters is the same as not turning the face at all.

The cubies have stickers on them, generally in one of six colors; the puzzle is solved when the cubies are arranged such that the stickers form six 3 x 3 squares of the same color, i.e. when the big cube looks like it is solidly colored on each side. The puzzle is then to take a Rubik's cube where the cubies have been scrambled and, via twisting the faces, return the cube to the solved position.

Since the invention of the cube, a myriad of methods for getting from a scrambled position to the solved position have been created. Some are hard to learn, some are easy to learn; some are slow, some are fast. Most methods are hard to simply stumble upon by accident; usually to come up with a new method requires lots of experimentation, during which the cube gets scrambled, although hopefully not beyond the experimenter's ability to solve.

Most people who pick up a Rubik's cube have some success the first few times, perhaps getting a few stickers of the same color onto a single face, perhaps even getting an entire face just by exploration. But that's usually the stopping point. After all, once you've gone through all that effort to get a face together, you don't want to destroy that. But turning any of the faces next to the solved face will move some pieces into the wrong position, undoing your hard work; so you're stuck with only being able to turn the face you've solved and the opposite face. What can you do now?

The secret is that to get the freedom to fix the rest of the cube, you have to temporarily undo your solved parts in such a manner that you can fix them after you've used that temporary freedom, without undoing the new fixes that you've achieved. As you solve more and more of the cube, this gets trickier and trickier.

Thus we get to the second part of solving the cube: planning. This doesn't mean you have to know every single step to take before even turning a face (although there are people who can do this) but you need to have an idea of "I want to solve these pieces first, and then those piece next, and then the rest of the pieces afterward". While less essential than the first part, the temporary-controlled-scrambling for freedom trade-off, this allows you to keep track of what kind of scrambling you're allowing at each step, how much control you need over that scrambling. You could be purely opportunistic and just solve whatever piece is easiest to slot into place, but if your solved pieces are scattered randomly around the cube then they're blocking all sorts of possible moves and are hard to move out of the way.

So most methods can be broken up into these two pieces, which I'll call "algorithms" and "plans". An algorithm in this case is a specific set of twists (e.g. twist the top face a quarter turn, then the right face a half turn, etc) that moves some number of cubes around, while also having some other cubes end up in the same positions that they started in. The first bunch of cubes are the ones you're trying to put into place, the second bunch of cubes are the ones that are already solved and that you're trying not to screw up. A plan is a sequence of bunches of cubes, in order of which ones you'll solve first. For instance, one plan might say "pick a face, put the edge pieces for that face in place, then the corner pieces in place, and then the edges next to those corners, etc". At each step of the plan, the algorithms will tell you the exact set of twists needed to execute that step of the plan; which algoirthm to use will depend on which step of the plan you're on and the actual position of the cubes involved.

While plans are often malleable and often involve some on-the-spot thinking, algorithms are usually just memorized, since they are much less flexible. Substituting a half-turn for a quarter turn can lead you quite far from where you wanted to go, but solving one particular corner before another often isn't too much of a stretch. Algorithms are also less flexible in terms of what they can do; a given algorithm moves a specific set of cubes around in a specific way and keeps a specific other set of cubes in the same place, so if that isn't quite what you want, you'll need a new algorithm. Some methods require memorizing hundreds or thousands of algorithms for particular situations; in return, they get speed, in that the more specific algorithms are also often faster than more general ones. So if you want speed, then you need to have a good memory. You also need to be able to recognize what needs to be done quickly, not wasting time choosing which cubes to get into position next. Hence the need for good plans.

But methods aren't the only things that go into speed. You need dexterity as well. Speed cubers often use all of their fingers individually when solving, and their wrists, so that once a face has been twisted they can go to the next move without having to reposition their fingers or the cube in preparation. Perhaps surprisingly, a lot of effort is put into the physical cube as well. A cube that requires a lot of strength to turn is not going to be good for speed cubning, nor is a cube whose faces won't stop spinning if you tap it accidentally. A good speedcube will be easy to turn, but the faces will stay put until deliberately twisted, and will twist exactly (or almost) a quarter, half, or three-quarter turn, as if you turn a face somewhere in between the other faces will usually refuse to budge. Of course, some speedcubers have learned to take advantage even of this constraint.

Interestingly, the fastest speedcubing methods are not the shortest, in that although someone using these methods can solve the cube in a very short time, there are other methods which involve fewer overall twists. Using fewer twists does make for a shorter solving time, all other things being equal, but these methods with few twists require the solver to spend a lot of time analyzing the cube at each step to determine which twist to do next, while someone focusing on speed will simply keep turning without regard for whether they're taking the absolute shortest (measured in twists) path or not. By the way, the absolute shortest path, if we measure a quarter twist, a half twist, and a three-quarter twist each as a single move, is known to be at most 20 moves long. This was proved definitively in 2010 using a computer running a lot of calculations. Unfortunately, nobody knows how to figure out those 20 moves for a given scrambled position. The shortest known methods take about 50 moves, and involve tons of memorization without much pattern.

Next time I'll get a bit into the math of the Rubik's cube, but for now I'll just note that there are over 40,000,000,000,000,000,000 possible positions for a standard, solid-colors Rubik's cube to be in. That's 40 followed by 18 0s. So someone who knows a general method for solving a Rubik's cube knows how to get from any of those 40 million million million positions to the solved position reliably, and it is possible to do so in only 20 moves.