The Rubik's Cube
The Rubik’s cube is a platonic solid with 6 congruent square faces. It is composed of 26 smaller cubelets; 8 of which are vertex pieces, 12 are edge pieces and 6 are center pieces.
Each vertex cubelet has three sides which indicates that it has three different possible orientations (shown below) and each edge cubelet has two sides which indicates that it has two different possible orientations.
As seen in the diagram for vertex cubelets above, the orientation of a piece is relative to its surrounding faces. This means that physically turning the entire cube does not change orientations; instead, rotating individual faces changes them.
There are 8! different ways to reposition all of the vertex cubelets and another 3 ways to orient each of them. This results in a total of 8! * 38 ways to configure all of the vertex cubelets. There are also 12! different ways to rearrange all of the edge cubelets and another 2 ways to orient each of them. Here, we have another total of 12! * 212 ways to configure all of the edge cubelets. Since the center cubelets do not move and each has only one possible orientation, there is only one way to position them. Combining these totals result in an upper bound of 8! * 38 * 12! * 212 different configurations of the Rubik’s cube. Based on this information, the group R = {S8 * ℤ38 * S12 * ℤ212} will be used to represent all of the possible configurations of the cube. Here, S8 and S12 are permutation groups of the vertex and edge cubelets and ℤ38 and ℤ212 are vectors specifying the orientation of the vertex and edge cubelets.
For further work with the Rubik’s cube it is useful to name the faces based on their location. We will refer to the 6 faces of the cube as front (F), right (R), left (L), up (U), down (D), and back (B).
There are 8! different ways to reposition all of the vertex cubelets and another 3 ways to orient each of them. This results in a total of 8! * 38 ways to configure all of the vertex cubelets. There are also 12! different ways to rearrange all of the edge cubelets and another 2 ways to orient each of them. Here, we have another total of 12! * 212 ways to configure all of the edge cubelets. Since the center cubelets do not move and each has only one possible orientation, there is only one way to position them. Combining these totals result in an upper bound of 8! * 38 * 12! * 212 different configurations of the Rubik’s cube. Based on this information, the group R = {S8 * ℤ38 * S12 * ℤ212} will be used to represent all of the possible configurations of the cube. Here, S8 and S12 are permutation groups of the vertex and edge cubelets and ℤ38 and ℤ212 are vectors specifying the orientation of the vertex and edge cubelets.
For further work with the Rubik’s cube it is useful to name the faces based on their location. We will refer to the 6 faces of the cube as front (F), right (R), left (L), up (U), down (D), and back (B).
It is also useful to name the vertex and edge cubelets. They will be labeled as shown in the diagrams below. The first shows the positions of the vertex and edge cubelets on a picture of the Rubik’s cube. The second shows their same positions on a simplified graph. Unlike on the first picture of the Rubik’s cube, all but one side of the cube is visible on graphs such as this. They will therefore be used to illustrate information throughout this paper.
As explained earlier, the orientation of a cubelet is relative to its surrounding faces. Each vertex cubelet will have an orientation of a 0, 1 or 2 (ℤ3) and each edge cubelet will have an orientation of a 0 or 1 (ℤ2). For purposes of this paper the defined zero sides, or sides with an orientation of 0, for each cubelet are shaded in the graph below.
For each edge cubelet, the side that is not defined as the zero side will by default have an orientation of 1. For vertex cubelets, the remaining sides will have an orientation of 1 and 2 working clockwise from the defined zero side, as shown below.
For a vector a = (a1, a2,…a8), an refers to the orientation of the vertex cubelet currently occupying position n. Similarly, for a vector b = (b1, b2,…b12), bm refers to the orientation of the edge cubelet currently occupying position m. We will refer to these vectors as orientation vectors.
It has already been noted that the group R formed by the Rubik’s Cube is a subset of S8 * ℤ38 * S12 * ℤ212. An element of this group will have the form X = (α, a, β, b) where α is the permutation of the vertex cubelets, a is the orientation vector of the vertex cubelets, β is the permutation of the edge cubelets and b is the orientation vector of the edge cubelets.
Here is a simple example which should help clarify how to find a configuration’s corresponding element in the group R. Suppose the only three cubelets that are out of place are the ones indicated in the picture below; all the other pieces are correctly positioned and oriented.
It has already been noted that the group R formed by the Rubik’s Cube is a subset of S8 * ℤ38 * S12 * ℤ212. An element of this group will have the form X = (α, a, β, b) where α is the permutation of the vertex cubelets, a is the orientation vector of the vertex cubelets, β is the permutation of the edge cubelets and b is the orientation vector of the edge cubelets.
Here is a simple example which should help clarify how to find a configuration’s corresponding element in the group R. Suppose the only three cubelets that are out of place are the ones indicated in the picture below; all the other pieces are correctly positioned and oriented.
The first step is to look at the permutation of the vertex cubelets. Cubelet 1 is now in the position of cubelet 4, cubelet 4 is located in position 2 and cubelet 2 is located in position 1. Since all the other vertex cubelets are in the correct position the result is a vertex permutation α =(1 4 2). For the vertex orientation vector we need to recall which faces have an orientation of zero. For vertex cubelets, the defined sides were the upper and down. (In this example the relevant ones have been marked with a white X) In position 1, the zero side belongs on the upper face but is now on the front face. This gives an orientation of 2 since the actual zero side of this cubelet is two faces away, clockwise, from the defined zero side. In position 2, the zero side belongs on the down face but instead it is on the right face. Again, the actual zero side of this cubelet is two faces away clockwise from the defined zero side so its orientation is 2. In position 4, the zero side should be on the upper face but it is on the front face. Here, the actual zero side is just one face away from the defined zero side resulting in an orientation of 1. The remaining pieces all have an orientation of 0 since they are correctly oriented. The resulting vector is a=(2,2,0,1,0,0,0,0). If any edge cubelets were out of place, the same process would be used to determine their correct permutation and orientation vector. The element in R for this example is therefore
A = ((1 4 2), (2,2,0,1,0,0,0,0), (1), (0,0,0,0,0,0,0,0,0,0,0,0))
The basic moves that the Rubik’s group is composed of are {F90, R90, L90, U90, D90, B90}. These stand for, respectively, rotating the front face, the right face, the left face, the upper face, the down face, and the back face 90 degrees clockwise. (Later in this paper they will just be written as F, R, L, U, D, B for simplicity) These moves will be referred to as the generators of the group because any configuration of the cube can be attained from a combination of them. Their corresponding elements in the group are as follows. The first element, F90, is illustrated with a diagram of the cube configuration.
The basic moves that the Rubik’s group is composed of are {F90, R90, L90, U90, D90, B90}. These stand for, respectively, rotating the front face, the right face, the left face, the upper face, the down face, and the back face 90 degrees clockwise. (Later in this paper they will just be written as F, R, L, U, D, B for simplicity) These moves will be referred to as the generators of the group because any configuration of the cube can be attained from a combination of them. Their corresponding elements in the group are as follows. The first element, F90, is illustrated with a diagram of the cube configuration.
F90 = ((1 2 3 4), (1,2,1,2,0,0,0,0), (1 2 3 4), (0,0,0,0,0,0,0,0,0,0,0,0))
R90 = ((1 5 6 2), (2,1,0,0,1,2,0,0), (1 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0))
L90 = ((3 7 8 4), (0,0,2,1,0,0,1,2),(3 10 9 8), (0,0,1,0,0,0,0,1,1,1,0,0))
U90 = ((1 4 8 5), (0,0,0,0,0,0,0,0), (4 8 11 5), (0,0,0,0,0,0,0,0,0,0,0,0))
D90 = ((2 6 7 3), (0,0,0,0,0,0,0,0), (2 7 12 10), (0,0,0,0,0,0,0,0,0,0,0,0))
B90 = ((5 8 7 6), (0,0,0,0,2,1,2,1), (11 9 12 6), (0,0,0,0,0,0,0,0,0,0,0,0))
You might assume calculating the remaining elements of the group would be as obvious as combining respective permutations and adding vectors of the generators. This however is not the case because the positions of cubelets have an effect on the orientations. As a result, the combination of any two moves, X = (α, a, β, b) and
Y = (δ, d, ε, e) gives the result X⋅Y = (αδ, a+αd, βε, b+βe). This is an example of a specialized product of two groups called a semidirect product.
To illustrate the need for using the semidirect product operation for this group, an example is provided below. We will compare the resulting elements from combining two moves by inspecting the diagram (as was done in the first example) and then by using the group operation. The two answers should agree which will show that the group operation is in fact more complicated than the obvious algebraic combination. The group operation will be used since it is more efficient to combine moves using a formula than to create a new diagram for every configuration. In the following example, the two moves that will be combined are first rotating the front face and then the right face 90 degrees clockwise.
R90 = ((1 5 6 2), (2,1,0,0,1,2,0,0), (1 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0))
L90 = ((3 7 8 4), (0,0,2,1,0,0,1,2),(3 10 9 8), (0,0,1,0,0,0,0,1,1,1,0,0))
U90 = ((1 4 8 5), (0,0,0,0,0,0,0,0), (4 8 11 5), (0,0,0,0,0,0,0,0,0,0,0,0))
D90 = ((2 6 7 3), (0,0,0,0,0,0,0,0), (2 7 12 10), (0,0,0,0,0,0,0,0,0,0,0,0))
B90 = ((5 8 7 6), (0,0,0,0,2,1,2,1), (11 9 12 6), (0,0,0,0,0,0,0,0,0,0,0,0))
You might assume calculating the remaining elements of the group would be as obvious as combining respective permutations and adding vectors of the generators. This however is not the case because the positions of cubelets have an effect on the orientations. As a result, the combination of any two moves, X = (α, a, β, b) and
Y = (δ, d, ε, e) gives the result X⋅Y = (αδ, a+αd, βε, b+βe). This is an example of a specialized product of two groups called a semidirect product.
To illustrate the need for using the semidirect product operation for this group, an example is provided below. We will compare the resulting elements from combining two moves by inspecting the diagram (as was done in the first example) and then by using the group operation. The two answers should agree which will show that the group operation is in fact more complicated than the obvious algebraic combination. The group operation will be used since it is more efficient to combine moves using a formula than to create a new diagram for every configuration. In the following example, the two moves that will be combined are first rotating the front face and then the right face 90 degrees clockwise.
The element for this configuration of the cube can be found using the same method of inspecting the graph as used in the first example. First, the vertex permutation and orientation vector should be found. Here, α = (2 3 4 5 6) and a = (1,1,1,2,2,2,0,0). Also, the resulting edge permutation is β = (1 2 3 4 5 6 7) and orientation vector is b = (1,0,0,0,1,1,1,0,0,0,0). The element in the group R that these moves produce is
R90⋅F90 = ((2 3 4 5 6), (1,1,1,2,2,2,0,0), (1 2 3 4 5 6 7), (1,0,0,0,1,1,1,0,0,0,0))
Using the group operation to combine these moves is shown below. (Note: permutations are calculated from right to left)
F90 = (δ, d, ε, e) = ((1 2 3 4), (1,2,1,2,0,0,0,0), (1 2 3 4), (0,0,0,0,0,0,0,0,0,0,0,0))
R90 = (α, a, β, b) = ((1 5 6 2), (2,1,0,0,1,2,0,0), (1 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0))
R90⋅F90 = (αδ, a+αd, βε, b+βe)
= ((2 3 4 5 6), (2,1,0,0,1,2,0,0) + (1 5 6 2) ∙ (1,2,1,2,0,0,0,0), (1 2 3 4 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0) + (1 5 6 2) ∙ (0,0,0,0,0,0,0,0,0,0,0,0))
= ((2 3 4 5 6), (2,1,0,0,1,2,0,0) + (2,0,1,2,1,0,0,0), (1 2 3 4 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0) + (0,0,0,0,0,0,0,0,0,0,0,0))
= ((2 3 4 5 6), (1,1,1,2,2,2,0,0), (1 2 3 4 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0))
It is easy to see that the positions of the vertex and edge cubelets permute the elements in the corresponding orientation vectors. Also, the combination of these moves results in the same answer regardless of the method used. Had the two elements been added as originally expected, the result would be ((2 3 4 5 6), (0,0,1,2,1,2,0,0), (1 2 3 4 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0)) which is incorrect as shown by a quick inspection of the cube configuration.
Using the group operation to combine these moves is shown below. (Note: permutations are calculated from right to left)
F90 = (δ, d, ε, e) = ((1 2 3 4), (1,2,1,2,0,0,0,0), (1 2 3 4), (0,0,0,0,0,0,0,0,0,0,0,0))
R90 = (α, a, β, b) = ((1 5 6 2), (2,1,0,0,1,2,0,0), (1 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0))
R90⋅F90 = (αδ, a+αd, βε, b+βe)
= ((2 3 4 5 6), (2,1,0,0,1,2,0,0) + (1 5 6 2) ∙ (1,2,1,2,0,0,0,0), (1 2 3 4 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0) + (1 5 6 2) ∙ (0,0,0,0,0,0,0,0,0,0,0,0))
= ((2 3 4 5 6), (2,1,0,0,1,2,0,0) + (2,0,1,2,1,0,0,0), (1 2 3 4 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0) + (0,0,0,0,0,0,0,0,0,0,0,0))
= ((2 3 4 5 6), (1,1,1,2,2,2,0,0), (1 2 3 4 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0))
It is easy to see that the positions of the vertex and edge cubelets permute the elements in the corresponding orientation vectors. Also, the combination of these moves results in the same answer regardless of the method used. Had the two elements been added as originally expected, the result would be ((2 3 4 5 6), (0,0,1,2,1,2,0,0), (1 2 3 4 5 6 7), (1,0,0,0,1,1,1,0,0,0,0,0)) which is incorrect as shown by a quick inspection of the cube configuration.