User:Josephbrophy/Sandbox

Permutations

The original (3×3×3) Rubik's Cube has 26 cubelets, of which eight are three sided corner pieces, twelve are two sided edge pieces, and six are one sided center pieces, as shown in the partially disassembled cube immediately above. Some experts argue that the center piece is one piece with six sides, so the definition may depend on the construction of the cube.

The number of permutations of the solvable original (3x3x3) Rubik’s Cube are not intuitively obvious because of limitations or parity requirements inherent in the mechanics of the cube. The simplest way of gaining an understanding is to first start with the disassembled cube and assemble it at random. A second point worth considering is that the corner, edge, and center pieces represent separate solution domains. They can be solved independently of each other, and consequently, their permutations are determined independently of each other.

Corner pieces: Working from a disassembled cube, the first randomly selected corner piece of the eight corner pieces can be placed in any of eight corner locations. The second randomly selected corner piece can be placed in any of the remaining 7 corner locations. The 6th in any of 6 locations, the 5th in any of 5 locations, and so forth. This produces 8×7×6×5×4×3×2×1 or 8! or 8 factorial permutations. Each corner piece has three sides with three different colors and consequently three different visual orientations. When the cube is being assembled, each corner piece can placed in any location and in any one of its three orientations. This produces another permutation factor of 3×3×3×3×3×3×3×3 = 3⁸.

The total corner permutations from a disassembled cube = 8!×3⁸ = 264,539,520 possibilities. But not all of these possibilities produce a solvable cube.

When one attempts to solve the Rubik’s Cube, it is soon discovered that there are limitations in the mechanics of the cube. For example, when one attempts to rotate a corner piece in a clockwise (CW) direction, to change its orientation using the “swap series”, (citation needed) another corner piece will be rotated in an offsetting counter-clockwise (CCW) direction. One soon learns that when rotating a corner piece, three other corner pieces are rotating at the same time, and that the sum total of all the changes in orientation must be equal to zero or congruent (mod3). Supporting this observation is a mathematical theorem stating that a corner piece cannot change color orientation by itself.^[1]^[2] Consequently, one degree of freedom is lost when working with corner pieces because the orientation of the final corner piece is predetermined by the other corner orientations.

The total corner permutations of a solvable cube, therefore is = 8!×3⁷ = 88,179,840 possibilities.

Edge pieces: The type of reasoning used for corners, also applies to the Edge Pieces. The first randomly selected edge piece can be placed in any one of 12 locations. The 11th in any of 11 locations, etc. producing a permutation of 12×11×10×9×8×7×6×5×4×3×2×1 or 12! or 12 factorial. Since edge pieces have two sides with distinguishable colors or two orientations, it produces an orientation permutation factor of 2×2×2×2×2×2×2×2×2×2×2×2 or 2¹².

The total edge permutations from a disassembled cube, therefore = 12!×2¹² = 1,961,990,553,600 possible arrangements. However 25% of these arrangements produce an unsolvable cube for reasons described below.

There is a mathematical theorem that states that an single edge piece can not be flipped by itself.^[3] ^[4] When working with edge pieces one soon discovers that the change in orientation of edge pieces can only occur in pairs. For example, even when working with “[triangle series]”(citation needed) to manipulate three edges at a time, one discovers that two edges will flip, and the third edge will effectively double flip, always producing an even number of changes in orientation. So one degree of freedom is lost producing an orientation permutation factor of only 2¹¹ instead of 2¹². Additionally, only half of the 12! permutations for location produce an even number of paired edges with a relatively correct orientation. The other half of the permutations contain an inconsistent relative pairing of edge pieces required for a solvable cube. So the 12! permutations must be adjusted by a factor of 50% or by a divisor factor of 2.

This can be demonstrated simply by a summation of the coefficients of an expansion of the binomial (E + O) ¹², where E (even) represents an edge piece that is congruous with its center piece and O (odd) represents an edge piece that is incongruous with its center piece:

(E+O)^{12}=\sum _{k=0}^{12}{12 \choose k}x^{12-k}y^{k}\quad where:

{12 \choose k}={\frac {12!}{k!\,(12-k)!}}

The reader is left to carry out the calculations, but it's not really necessary, the actual results can be achieved through reasoning. For example the sum of the [[Binomial coefficient|binomial coefficients = 2¹² = 4096. Further reasoning reveals that when the exponents of E and O are even, all E edges can be paired and all O edges can paired. When the exponents are odd, an E edge piece will have to be paired with an O edge piece, producing an unsolvable configuration. Simple observation also shows that the binomial is symmetrical, so without carrying out the calculations, one can deduce that half of the 4096 configurations are even and solvable and the other half are odd and not solvable. So one degree of freedom is lost.

The total edge permutations for a solvable cube, therefore = (12!/2)×2¹¹ = 490,497,638,400.

Center pieces: the relative location of the center pieces to each other can be fixed or variable depending on the how the cube is manufactured. For sake of brevity in this section we are assuming the relative location of the center faces is fixed and therefore has but one permutation. However, each center face has four potential orientations or 4×4×4×4×4×4 = 4⁶ = 4096 permutations.

Since the faces are not marked and their visual orientations are indistinguishable with respect to the solution of the original Rubik’s cube, for sake of brevity in this section, we are assuming the number of permutations of the orientation of the center faces one. The discussion of permutations of the center pieces will be continued in the section Center faces following.

The total permutations of an assembled (3×3×3) original cube is given by: ${8!\times 3^{8}\times 12!\times 2^{12}\times (1)\times (1)}\approx 5.19\times 10^{20}$ or precisely = 519,024,039,293,878,272,000 or 519 quintillion

The total permutations of a solvable (3×3×3) original cube is given by: ${8!\times 3^{7}\times (12!/2)\times 2^{11}\times (1)\times (1)}\approx 4.33\times 10^{19}$ or precisely = 43,252,003,274,489,856,000 or 43 quintillion.^[5]

Center faces

The original Rubik's Cube had no orientation markings on the center faces, although some carried the words "Rubik's Cube" on the center square of the white face, and therefore solving it does not require any attention to orienting those faces correctly. Marking the Rubik's Cube increases its difficulty because this expands its set of distinguishable possible configurations.

For example, if one has a marker pen, one could mark the central squares of an unscrambled Cube with four colored marks on each edge, each corresponding to the color of the adjacent face. Some Cubes have also been produced commercially with markings on all of the squares, such as the Lo Shu magic square or playing card suits. Thus one can nominally solve a Cube yet have the markings on the centers rotated; it then becomes an additional test to solve the centers as well.

The center pieces can be rotated without disturbing the corners or edges but it requres the rotation of two center faces at a time. The simplest algorithms are slow and tedious requiring 105 turns.^[6] When the Cube is unscrambled apart from the orientations of the central faces, there will always be an even number of squares requiring a quarter turn because of parity restrictions inherent in the mechanics of the cube which apply to the center faces as well. If the central faces are linked by color markings to the adjacent faces as described in the previous paragraph, then one degree of freedom is lost reducing the number of permutations from 4⁶ to 4⁶/2.

The total permutations of an assembled (3×3×3) original cube with synchronized color marked center faces is given by: ${8!\times 3^{8}\times 12!\times 2^{12}\times (1)\times 4^{6}}\approx 1.77\times 10^{23}\approx 1.77\times 10^{23}$ or precisely = 177,160,205,412,310,450,176,000 or 177 sextillion.

Finally, the total permuations of a solvable (3×3×3) original cube with synchornized color marked center faces is given by: ${8!\times 3^{7}\times (12!/2)\times 2^{11}\times (1)\times (4^{6}/2)}\approx 8.858\times 10^{22}$ or precisely = 88,580,102,706,155,225,088,000 or 88 sextillion

Here is yet another twist. If the Center Faces have a picture rather than synchronized color markings, then the entire cube does not have a fixed orientation in space, and can be rotated freely to any starting position. Thus one set of orientations is free or effectively eliminated, reducing the potential configurations to 4⁵ = 1096 permutations. Because of parity restrictions the total number of solvable configurations would be reduced to 4⁵/2 = 512 permutations.

The puzzle is often advertised as having only "billions" of positions, as the larger numbers could be regarded as incomprehensible to many. To put these numbers into some perspective, if every permutation of a 57-millimeter Rubik's Cube were lined up end to end, it would stretch out approximately 261 light-years (which is a distance not a time.) This distance is large enough to provide us with 31 round trips from planet Earth to our closest star, Proxima Centauri. Or it would provide us with about 1.6 million round trips from the Sun to the Planet Jupiter. Alternatively, if laid out on the ground, there would be enough cubes to cover the earth with 273 layers of cubes, recognizing the fact that the radius of the earth sphere increases by 57 mm with each layer of cubes.

[1]
Ryanheise "Rubik's Cube Theory": Laws of the cube
[2]
Chris Godbout "Group Theory and the Rubik’s Cube": Paper April 2008
[3]
Ryanheise "Rubik's Cube Theory": Laws of the cube
[4]
Chris Godbout "Group Theory and the Rubik’s Cube": Paper April 2008
[5]
Martin Schönert "Analyzing Rubik's Cube with GAP": the permutation group of Rubik's Cube is examined with GAP computer algebra system
[6]
"Rotating the center faces": Rotating the center

Related Articles