Thursday, October 6, 2011

How not to solve a Rubik's Cube

The Rubik's Cube is one of my favorite puzzles. Upon first glace at a sufficiently scrambled cube, one might feel an instant feeling of dismay. With so many combinations, how could anyone hope to figure out how to unscramble it in a reasonable amount of time?

Many people would give up right then and there. But Rubik's Cubes have been solved countless times by countless people. It's far from an unsolvable problem, and in fact many of us take our fun from the thrill in the challenge.

I have successfully solved a Rubik's Cube on a number of occasions. I'm far from an expert solver, or a speed solver, generally it'll take me a couple of hours to solve an arbitrarily scrambled cube, not because it takes that long, but because I can only do it in stages and spending too long on a single stage get's my brain a little wonky :)

I remember the first time I solved the cube was right around the time of my thirteen birthday. Being proud, I continued to play with the solved cube until I accidentally scrambled it again. To my initial frustration, I then had to solve it a second time, which I did. It was promptly buried in the backyard after that.

(Aside: It was buried not because it frustrated me to the point I wanted to get rid of it, but we also happened to be making a Time Capsule at the same time and I thought it would make a good addition. That Time Capsule I believe is due to be unearthed next summer actually.)

Nevertheless, puzzle solved, I prompt forgot about the device for a number of years. Fast forward to several months back when I happened to see one at a local department store and decided to buy it.

I've solved this cube a couple of times since then, this time things are a little different however. Instead of just solving the cube once and forgetting about it, over time I'm practicing on it, trying to become better at solving it so that I can solve it in general for any specific cube without help.

To be fair, I've never actually solved a cube, from scratch, without some sort of assistance. Even when I solved the first cube all those years ago, I had a sort of guide that came with the cube. Now, this guide was far from a defacto "here are step by step solving instructions", but rather just a general set up "helper" steps to get where you wanted to go.

These helper steps are called algorithms, and are basically a short (or long) set of instructions on how to take the cube in one configuration and get it to another configuration. For example, how to move a block on the bottom, to the top, without changing a series of surrounding cubes (but not all cubes). I've always used these to help me, though again, even with this set of helper steps solving the cube is still fairly difficult. You still need to get it the right stage to do perform the algorithm, and could make other unwanted changes as well. Assembling them all together to solve the cube is still the hard part.

Some might label using the algorithms as "cheating", but to me, cheating at a cube would be more akin to rearranging the stickers or taking the cube apart (as many, including my original, are capable of being dismantled) and reassembling it correctly. Even expert speed solvers use these algorithms, likely taught to them by a book or someone else, or perhaps learned from scratch in some cases. Using algorithms is just a natural part of learning how to solve the cube. I suppose you could invest many hours in addition to actual solving time to develop the algorithms, or it may just be the software engineer in me which has taught me to use what's already been developed and not waste time reinventing the wheel :)

But in fact, this blog post is not about how to solve a Rubik's Cube. There are many other sites for that, one of my favorites is linked here: http://www.chessandpoker.com/rubiks-cube-solution.html

No, rather this post is about how *not* to solve a Rubik's Cube. But wait, you cry, why would anyone care about how not to solve the cube?

The answer is that there is an oft-quoted, but misguided, way that people often use to try and solve the cube. When someone first starts trying to solve it, they might start by randomly twisting sides in the hope they'll get somewhere. This procedure is doomed to fail (unless maybe you happen to be a computer program with dozens of gigabytes of memory). But rather, the misconception among novice cubers seems to be that there exists a fixed sequence of moves (moves, which I'll define below) which will solve the cube regardless of it's starting configuration (we'll call this the Magic Sequence). So a cuber with this mindset will spend all of his or her time searching for the Magic Sequence, without actually really paying attention to the mechanics of the cube.

In fact, searching for the Magic Sequence is at least equally (in fact more so) doomed to fail then twisting the cube randomly. I suppose even random twists could conceivably solve the cube eventually even if it takes eons. But trying to use a single set to solve the cube regardless of it's starting configuration is simply impossible, as I will demonstrate here. And so, it's important to explain why this method can't work and that a cuber trying to use it will ultimately never succeed.

First, let's consider what I mean by a "move". Among cubers, "moves" can have a variety of meanings, anything from a single turn to an entire algorithm. However, a common definition for a move often used by newer cubers and people searching for the Magic Sequence is a single turn, either clockwise or counter clockwise, of one of the cube's six sides (sometimes called a Quarter Turn by cubers).

Now, if you'll consider it, what is the cube actually made of? In fact, a Rubik's Cube is not a singular cube, but rather 26 smaller cubes (9 on each end, plus 8 going in a ring down the middle. There is no dead center cube, as that's where the rotation mechanism lives).

We can easily enumerate each of of these smaller 1-26 cubes and keep track of their orientation as we work the cube. Keep in mind that this enumeration would exist regardless of the color of each "face" of the cube.



Thus, from any starting configuration, there are only 12 possible unique moves, by this definition, that we can make to get the cube in a new configuration:

1. Top layer goes clockwise or counter clockwise
2. Bottom layer goes clockwise or counter clockwise
3. Right layer goes clockwise or counter clockwise
4. Left later goes clockwise or counter clockwise
5. Front later goes clockwise or counter clockwise
6. Back layer goes clockwise or counter clockwise

Here is an illustration of 6 of the 12 possible moves. The other 6 are just mirrors on the non-visible sides.







Some people might try to argue that there are more moves then this. For example, turning the bottom two layers clockwise. But, this is really equivalent to turning the top later counter-clockwise. Likewise, turning the right layer clockwise twice is really just two applications of the same unique move. Each move will have a fixed, predetermined affect on the cube that can't be altered.

A solved cube, with all sides showing the same color, will live as one, and only one, possible configuration of the individual cubes. The cube can only exist in a single configuration at a time, it cannot exist in two different states simultaneously. Agreed? This is Rubik's cube, not Schrodinger's cube, after all.

Let's say that I start with the cube in a given configuration, called Configuration A. I then perform a sequence of moves on the cube (where a sequence is an ordered set of the twelve moves listed above). We'll call this Sequence A. Upon applying Sequence A, to Configuration A, we end up in another Configuration B (which could possibly be equal to Configuration A). The important thing to remember is that every time I start the cube in Configuration A, and apply sequence A, I'll *always* end up in Configuration B. Likewise, if I start the cube in Configuration B, and perform Sequence A backwards, I'll always end up with Configuration A. This is true for all possible Configurations and Sequences of the cube. There is no possible sequence that I can perform on a configuration such that applying the same sequence to the same configuration will result in multiple configurations. Make sense? The diagram below shows the symmetric nature of applying a sequence to a configuration.



Given that, to disprove the "Magic Sequence", we can use what's called a proof by contradiction. The basic premise is that if we can show that the existence of a magic sequence would lead to a contradiction given the rules of the cube we've described (cannot exist in more than one state, and configuration + sequence = a single new configuration), then it can't exist.

Let's call a cube's solved state Configuration Z.
First, let's imagine that the "Magic Sequence" did exist. This would mean that there exists a sequence such that I can apply the sequence to Configuration A and end up with Configuration Z, and that I can apply the identical sequence to Configuration B, and end up with Configuration Z, (where A and B are *not* the same configuration, and represent any configuration the cube could be in).

But then, what would happen to Configuration Z if I performed the "Magic Sequence" backwards? Remember that we stated the cube could only exist in one configuration at any one time.

If the "Magic Sequence" existed, then I'd be able to perform it backwards from the solved state (Configuration Z) and end up with *both* Configuration A AND Configuration B, which is impossible, since the cube can only be in one configuration at a time. In other words, I can't apply the "Magic Sequence" to Configuration Z, and wind up with A, then later apply the same sequence to Configuration Z, and wind up with B, since a fixed sequence of moves will always have the same result on the cube. Therefore, the "Magic Sequence" does not exist.



Make sense?

Now, there are plenty of other ways to solve a cube. Many of them involve the application of multiple algorithms in order, which is sort of like a Magic Sequence. But the important distinction is that the algorithms involve decision-making, e.g. applying a different algorithm next based on the result of the last. If such a "Magic Sequence" like the one disproved existed, you'd be able to solve the cube without any decisions.

Feel free to leave any questions or comments you might have below and I'll do my best to answer them!

Happy cubing!

3 comments:

  1. Excellent post! Like you said, I also find linear algebra quite fun, though sometimes difficult of course, that tool for calculating inverse matrices is really convenient. Thanks!

    ReplyDelete
  2. sorry, wrong post for my comment I was also reading this one :)

    ReplyDelete
  3. Thanks quo!

    No worries, if you'd like to repost the comment on the Linear Algebra article I can remove the comment(s) here. Totally up to you though :)

    Have a great day!

    ReplyDelete