43 QUINTILLION COMBINATIONS

### Rubik Cube, 43 Quintillion Combinations

Just how many combinations are possible on the standard Rubik cube? The answer, roughly 43 quintillion, is printed on the box, but let's try to justify it.

First notice that the movable shell of the cube consists of 8 corner blocks and 12 side blocks. The corners cannot be moved into side positions, nor can side pieces move into the corners. To first approximation, sides and corners can be analyzed separately. Furthermore, position and orientation can also be analyzed independently. Let's begin with the corners.

Suppose the top and bottom faces of your cube are colored blue and white respectively. Every corner piece has exactly one blue or white face. If this face is horizontal (i.e. located on the top or bottom surface of your cube), then that corner piece has orientation 0. If the piece must be rotated counterclockwise 120 degrees, in order to attain a 0 orientation, then its orientation is 1. (We are looking at the cube from a point just off the corner, extending the cube's main diagonal.) If the piece must be rotated clockwise 120 degrees to attain a 0 orientation, then its orientation is 2. Clearly all corners have orientation 0 at the start.

Twist the top face 90 degrees, and watch what happens to the four top corners. Their positions shift, but their orientations do not change. If the blue side of a corner block was a clockwise turn away from horizontal, then it is still a clockwise turn from horizontal after the move. Similarly, a bottom twist does not change any of the corner orientations. Next twist the front face clockwise. The block at the upper left has its orientation increased by 1, as does the block at the lower right. Of course, if the orientation was 2, it goes back to 0. This is mathematics mod 3. The other two corner blocks have their orientations increased by 2. The total of all the orientations of all the corners is increased by 1+2+1+2 = 6, which is 0 mod 3. By symmetry, this holds for the right, back, and left faces as well. No matter how many moves we make on the cube, the sum of the 8 corner orientations is always 0 mod 3.

Next we must show that the 8 corners can in fact attain all possible orientations, subject to the mod 3 constraint given above. Recall that TBLRFK represent clockwise turns of the top, bottom, left, right, front, and back faces, while their lower case counterparts represent counterclockwise turns. The transformation [rBRFBftFbfrbRT] increments the orientation of the upper right front corner, and decrements the orientation of the upper left front corner, leaving the rest of the cube undisturbed. By prepending a couple moves to this transformation, and undoing these moves at the end, we can bump the orientations of any two corners on the cube, without disturbing any other pieces in any way. Suppose we want to realize the orientations 21022011. Add 1 to the orientation of the first corner, while subtracting 1 from the last corner, until the first has orientation 2. Then do the same with the second corner, until its orientation is 1. Again, the last corner takes up the slack. When the seventh corner attains its desired orientation (1), the same is true of the eighth corner, since the 8 orientations always sum to 0 mod 3. There are therefore 3^7 possible corner orientations, and any of these can be applied to the cube after the fact. Hereinafter, we will ignore the orientation of the corners, and multiply by 2187 at the end.

The side pieces can be analyzed in a similar fashion. Let the orientation of a side piece be 0 if it is an even number of moves from start, 1 if it is an odd number of moves from start. Of course we need to prove this definition is not ambiguous. Might there be two paths back to start, one even and one odd? The answer is no, but we will need to use the theory of even and odd permutations to prove it. Consider the side piece at the top front. We have already said the top of our cube is blue; let the front face be red. Thus our side piece has a blue top and a red front. In theory, this side piece can be thought of as a miniature Rubik cube, a scale model of the larger cube that contains it. This miniature cube, 1/27 the volume of the original, has 4 other faces that are not visible, as they are hidden inside the larger cube. Give them the same colors as the corresponding faces on the larger cube. Now twist the front face clockwise, and our little side cube also spins clockwise. This permutes the six virtual colors on the small side-cube. We see that the blue side has spun around to the right, but we also imagine the green, white, and yellow faces of the side cube rotating around inside the larger Rubik cube. Each time the side cube moves, four of its six faces spin around in a cycle while the other two remain in position. This is an odd permutation. After an odd number of moves, the side cube is rotated through an odd permutation, whereas an even number of moves carries the side cube into an even permutation. Since a side cube cannot exhibit an odd and an even permutation simultaneously, there cannot be two paths back to start having odd and even lengths.

Now that we have a well-defined orientation function, analyze the sides using the same techniques that were applied to the corners. Whenever any face is twisted 90 degrees, each of the 4 side pieces moves one step closer or farther from its home. In other words, the orientation of each of the 4 side pieces is reversed. Yet the sum of all the orientations remains 0 (mod 2).

Now select an arbitrary pattern of 12 orientations, subject to the above mod 2 constraint. We must implement these 12 orientations without disturbing the corners in any way, or the positions of the side pieces. The transformation [FFRlTTrLtlTkRlTTrLFFKtLT] flips the orientations of two side pieces, and leaves the rest of the cube undisturbed. By prepending a couple moves to this transformation, and undoing these moves at the end, we can change the orientations of any two sides on the cube. If the first side piece exhibits the wrong orientation, flip it (along with the last side). Do the same with the second side, and so on up to the panultimate side. The last side will be correct, because the 12 orientations always sum to zero. Hereinafter, we will ignore the orientation of the sides, and multiply by 2^11 = 2048 at the end.

Since orientations are no longer a factor, number the corner cubes 1 through 8, and number their corresponding start positions 1 through 8. How many ways can these 8 corner pieces be distributed among the 8 corner positions? The transformation [RTrfTFRtrTT] swaps two corner pieces and leaves the other corners in their original positions. This is the key to swapping any two corners on the cube. The first swap moves any of the 8 corners into the first position, the next swap moves any of the 7 remaining corners into the second position, and so on. All 8! corner permutations are accessible.

Finally, the sides must be moved into position, without moving the corners. At first, all side permutations look accessible, and this is almost the case. However, permutation parity cuts this number in half. Consider a 90 degree twist of any face. Four corners march around in a cycle, an odd permutation. Similarly, four sides march around in a cycle, producing another odd permutation. After one move, corners and sides both present odd permutations. After two moves, corners and sides attain even permutations again. By induction, the parity of the two permutations is equal. If the corners are arranged in an odd permutation, then the sides will present an odd permutation (as a result of arranging the corners), and only odd permutations are accessible thereafter. The transformation [FFRlTTrL] exchanges three side pieces, leaving the corners intact. This is the key to cycling any three sides on the cube. Move any of 12 sides into the first position, using a third piece to complement the dance. Then move any of 11 pieces into the second position, and so on. Once the tenth piece is placed, the transformation cannot be applied again, because there are only two pieces left. However, these pieces will be in position, because the parity of the sides is determined by the parity of the corners. Thus there are 12!/2 accessible side permutations.

Finally we are ready to run the calculation:
8! * 12!/2 * 3^7 * 2^11 = 43,252,003,274,489,856,000.

If you have a friend who has mastered the cube, and you enjoy practical jokes, try the following. Physically take apart his cube. (Twist one face 45 degrees and gently pry a side piece out with a spoon.) Swap two corners, and put the cube back together. Then mix it up, and casually inquire, "So ... you can really solve this thing, eh?" I played this trick on a friend in college, who then spent several frustrating days trying to solve the cube that he thought he had mastered. :-)

There is a related question: how many "different" combinations are there? By different, we mean distinct relative to rotations and reflections. After all, the configuration that is attained by a single clockwise twist of the top face resembles the result of one clockwise twist of the front face. If we rotate the cube and reassign colors accordingly, the former becomes the latter. Since there are 48 possible rotations and reflections of the cube in 3-space, the approximate answer is 43 quintillion divided by 48, or just under a quintillion. This is not an exact answer, because some patterns exhibit symmetry, and do not actually have 48 distinct representations. I suspect the exact calculation entails the use of the Bernside Polya counting theorem, but it's been a long time since I took combinatorics.

Although the cube has not been completely analyzed, we can place a lower bound on its complexity. After one move, the cube can be in any of 12 different configurations. After two moves, the cube can attain, at most, 12^2 = 144 patterns (the actual number is 129). The number of configurations that lie within k moves of start is
1 + 12 + 12^2 + 12^3 + ... + 12^k = (12^(k+1) - 1) / 11.
When k = 18, the result is less than 43 quintillion. Therefore, some configurations are 19 moves from start. If 180 degree turns are considered moves, the base of the exponential function changes from 12 to 18, and some configurations are 16 moves from start.