Justin Pombrio


-

Rubik's Cubes

There are precisely 3,674,160 configurations of a 2x2x2 Rubik’s Cube.


First, we need some terminology. A 2x2x2 Rubik’s Cube is constructed out of eight cubies. Each cubie has three colored stickers on it. A configuration of the cube can be described by the positions of the cubies and which direction their stickers face. I’m going to call a possible cubie position a corner position. There are eight corners positions, the upper front left corner, upper front right corner, etc..

An algorithm is a sequence of moves. Each move rotates one of the six faces (Front, Back, Right, Left, Up, Down) some multiple of 90 degrees clockwise (1, 2, or 3). For example, F1 rotates the front face 90 degrees clockwise, F2 rotates the front face 180 degrees clockwise, and R3 rotates the right face 90 degrees counterclockwise (or 270 degrees clockwise).

I will prove that there are exactly 3,674,160 configurations of a 2x2x2 Rubik’s Cube. The state of the cube can be thought of as the composition of three components: the orientation of the cube, the permutation of the cubies, and the rotation of each cubie.

The orientation of the cube can be changed by not performing any moves, but by simply rotating the whole cube. There are 24 orientations for each configuration of the cube: any of the 6 faces can be on top, and any of the 4 adjacent faces can be in front.

The permutation of the cubies tells which corner position each is in. There are 8 factorial, or 40320 conceivable cubie permutations: the first cubie might be at any of the eight corners, the second in any of the remaining seven, and so forth.

It turns out that all 40320 permutations are possible. Two adjacent corners may be swapped using the algorithm R3 F1 R3 B2 R1 F3 R3 B2 R2 U3. (Try it! You can use a 3x3x3 cube - just realize that its eight corners act like a 2x2x2 cube.) This swaps the upper-front-left and upper-front-right cubies. See nerdparadise. You can this algorithm multiple times to swap any two corners. For example, suppose you want to swap two opposite corners 1 and 4 using two intermediate corners ‘2’ and ‘3’. Use the following sequence of swaps: 1 2 3 4 -> 2 1 3 4 -> 2 3 1 4 -> 2 3 4 1 -> 2 4 3 1 -> 4 2 3 1. Now that you know how to swap any two cubies, it should be fairly clear that all permutations are possible.

Now lets look at rotations of the cubies. There are 3 ^ 8, or 6561, conceivable rotations of the cubies: each of the eight cubies might be rotated in three possible ways. But it turns out that only 3 ^ 7, or 2187, rotations are possible. I’ll call the configurations with one of these 2187 possible rotations valid, and then prove that only valid configurations are possible.

Start with a solved cube. Paint its top and bottom white. Pick four non-adjacent corners, and call them the even corners. Call the others the odd corners. Define the value of an even corner to be 0 if its white side faces up or down, 1 if it faces front or back, and 2 if it faces right or left. Likewise, define the value of an odd corner to be 0, 2, or 1 respectively. Now define the residue of a configuration to be the sum of the values of its corners modulo 3. A configuration is valid if its residue is zero.

First, I will prove that no sequence of moves yields an invalid configuration. This is because the residue of a cube configuration is invariant; it stays the same every time you make a move. First consider 90 degree rotations of the top and bottom faces. They effect four cubies, two odd and two even. They leave up/down faces alone, and transform front/back faces into left/right faces and vice-verse. Thus the value of each effected cubie stays the same, and the residue does not change. Next consider 90 degree turns of the front, back, left, and right faces. You can check that each of these moves either increases the value of each even cubie by 1 and decreases the value of each odd cubie by 1 modulo three, or vice-verse. So again, the residue stays the same. Since every move preserves the residue, and the solved configuration has residue 0, every valid configuration, that is every configuration you can reach by legal moves (no disassembling the cube), has residue 0.

Now I have to prove that you really can get to any of the 2187 possible rotations of the cubies. This can be accomplished just using the algorithm R3 D1 R1 F1 D1 F3 U3 F D3 F3 R3 D3 R1 U1 (see magliery), which simultaneously rotates the upper-front-left cubie counterclockwise and the upper-front-right cubie clockwise, while leaving all other cubies untouched. If you chain these together, you can simultaneously rotate any cubie clockwise, and any other counter-clockwise. Use this ability to cancel out cancel out pairs of cubies that have valus 1 and 2, by making both 0. The non-zero cubies left must all have the same value - either 1 or 2 - and there must be 0, 3, or 6 of them. You can use the algorithm twice to cancel out three 1s or three 2s, finally making all cubies have value 0. This is a method to get from any cubie rotation to the zero cubie rotation. To get from any cubie rotation to any other cubie rotation, first use this method to get to the zero rotation, then use it in reverse to get from the zero rotation to the other rotation.

So here’s the results: there are 40,320 possible permutations of the cubies, and 2187 possible rotations of the cubies, giving 88,179,84 possible states of the cube. But we’re overcounting, really - if you can reorient one state to get another one, they aren’t that different. Each configuration has 24 orientations, so there are only 88,179,840 / 24 = 3,674,160 configurations.