EXPLAIN EXTENDED

It's the holiday season again. This time of year, in between shopping, visiting friends and watching old movies on TV, I really like to solve puzzles. I like them all: crossword puzzles, jigsaw puzzles, logic puzzles, you name it. But one thing I never quite learned to solve is most popular puzzle in the world, the Rubik's Cube. It's time to fill the gap!

This year, we will be solving the Rubik's Cube in SQL.

The Rubik's Cube probably needs little introduction, but just in case. This is a small plastic cube made of 3×3×3 = 27 smaller cubes (called cubies in the community's parlance). It's equipped with a clever mechanism which lets you turn its faces about all six axes. Initially, the cubies are positioned so that every face has its own uniform color, but as you turn the faces in different directions, all the colors mix and spread around. Your goal is to restore the original colors by putting the cubies back in place.

The cubies in the centers of the faces never move relatively to each other. The red center always opposes the orange center, the blue the green, and the white the yellow. Also, if you look at the red, white and blue centers, they will always run clockwise in that order. No matter how you turn the faces on the cube, the center cubies will always stay this way.

Each cubie is unique. Apart from the center cubie in the middle (which we never see) and the six face center cubies, there are 8 corner cubies (with three stickers on them) and 12 edge cubies (with two stickers on them). In a solved cubie, all faces have the same color. This means that every corner cubie has its own unique set of colors, and every edge cubie too. The blue-white edge is the one sitting on the blue and white faces in a solved cube, and so it. Naturally, it means that there's no such thing as a red-orange edge or a red-orange-green corner (because the red face opposes the orange). Since the stickers stay on the cubies as we move them about, we can just name the cubies by their colors. There is only one red-white-blue corner which would move about but always stay red-white-blue.

When the cube is scrambled, it might seem to the untrained eye that the cubies can turn any old way. Yet, that's not the case. Because of the way the mechanism works, there are certain principles that limit the cubies' positions. For instance, no matter how you turn the cube, you cannot make a single corner or a single edge cubie turn in its place, or make just two cubies trade their places, with all the rest staying in place. These limitations are known as cube laws. In fact, if you take the cube apart and put the cubies back in random order, there's only one chance in 12 that you will get it right (i.e. you make a cube that can be solved by making legal turns). It will come handy later.

To describe a cube scramble, we could just list the stickers' colors ("the colors on the face with the red center, counting from the red-white-blue corner clockwise are red, white, yellow, green…") or cubie positions ("the red-yellow-green corner cubie is between the orange, white and green faces…"). But turns out, there is another way.

Similar to other famous combination puzzles, the Rubik's Cube runs on group theory. Even the Wikipedia page on group theory is illustrated by nothing else than an image of a Rubik's Cube. For those wishing to delve into the finer detail, there's a nice article on Wikipedia on the Rubik's Cube group. For the rest of us laypeople, this means that every valid state of the cube can be described by the sequence of moves (face turns) that have lead to this state. Come to think of it, that's only natural: if the cube came out of the box solved and we only scrambled it using the legal moves, then if we replay these moves on another cube, we will get the same scramble with the same colors. So, instead of naming the colors or cubies' positions, we can just say "take a solved cube, turn the white face clockwise, then the red face counterclockwise, then…"). In the end, it will be the same thing.

Note that in the previous paragraph I said that it would be possible, not that it would be easy. In fact, if we take a scrambled cube described by the series of moves from the solved cube, and replay these moves in reverse, we will get back to the solved cube. And that's the very essence of the problem: how do we, looking at a scrambled cube, find the sequence of moves that has lead to this particular state? Once we find the answer to this question, we'll just need to reverse this sequence and the cube will be solved. This answer, however, is not trivial to find.

Read the rest of this entry »