Rubik’s Magic Cube

Rubik’s Cube is a classic fad from the ’80s. Invented by architecture professor Ernő Rubik in 1974 as an illustration of design principles, it became an immensely popular puzzle for a while. Now it’s a hallmark of geekiness — when I visited Dartmouth I saw at least six or seven floating around the graduate student lounge.

What’s most interesting to us here is that it’s also a big case study in group theory. The official website has a pretty good Java implementation, for those who don’t remember (or who have repressed their memories of) the cube. I’ll start talking about the cube after the jump.

The cube is broken into 27 small “cubies”. There are eight corner cubies with three colors on each, twelve edge cubies with two colors each, six face cubies with one color each, and a single central cubie hidden in the middle of the cube. We can shuffle around the corners in 8! (8*7*6*5*4*3*2*1) ways, and rotate each corner three ways. We can shuffle the edges 12! ways and flip each one two ways. We’ll consider the faces of the cube to be fixed in place, providing an orientating framework that the edges and corners can move around. That means we have a total of 12!*2¹²*8!*3⁸ = 519,024,039,293,878,272,000 different states of the cube. Rotating a side of the cube shuffles around these states, so the six different rotations generate a group acting on the set of states! Not all such transformations are distinct, though. Rotating the same side four times in a row always brings us back where we started. In fact, there’s a normal subgroup of sequences of rotations that always bring us back where we started. The group of all sequences of rotations modulo the subgroup of “trivial” transformations is the Rubik’s Group .

Now, Rubik’s group can’t send every state to every other state. There are three pieces of data about the state of the cube that every member of leaves the same. We can’t rotate a single corner cubie and leave everything else the same, we can’t flip a single edge cubie and leave everything else the same, and the permutations of the corners and the edges are either both even or both odd (remember what we mean by “even” and “odd” permutations). I’ll prove the last one here.

For the moment, forget about the orientation of each cubie. Just think about the space around the cube that it occupies — its “cubicle”. Now think of rotating one side. This takes the four corners on that side and cycles them around, and also takes the four edges on that side and cycles them around. Remember that a four-cycle is an odd permutation, so rotating a side of the cube gives an odd permutation of both corners and edges. Every time we do another rotation we do another odd permutation on each set of cubies, so after rotations we either have both even permutations (if is even) or both odd permutations (if is odd). We just can’t do an even permutation of edges and an odd permutation of corners.

So, the restriction on corner orientations cuts down the states we can reach by a factor of 3, the restriction on the edge orientations gives a factor of 2, and the restriction on the signs of the permutations gives another factor of 2. It turns out that everything else is a possible transformation, which I’ll try to prove eventually. This means that the set of all states consists of 12 orbits, each containing 43,252,003,274,489,856,000 states.

Rubik’s Group also has 43,252,003,274,489,856,000 elements. To see this, notice that no two elements of the group can induce the same transformation of states. If we have sequences of rotations and that both act on the set of states the same way, then would send every state back to itself, meaning that this composition of rotations lives in the subgroup . But that means that is the identity in Rubik’s Group (the quotient of all rotation sequences by ) so and are the same in . Given two states in an orbit there’s exactly one way (modulo ) to get from one to the other, so has 43,252,003,274,489,856,000 elements.

I’ll be writing more about this in later posts as more and more tools of group theory come into our grasp. For now, I’ll end with a little note about how truly ginormous this number is. The marketing department back when Rubik’s Cube was first sold slapped a note on each package saying “more than 2 billion possible combinations”. In fact, there are more than twenty billion times more. To get a grasp on this sort of magnitude, remember the McDonalds’ signs that used to count up to “over 99 billion served”. Imagine changing that to “over 5 served”. That’s how far they underrated the number of states of the cube. And yet I hope to show that using group theory we can tame this hugely complicated beast and understand not only how to solve the cube, but why our solutions work.