This is an original research article by Yash Mantri (20/11/20)
“We turn the cube, and it twists us” – ERNO RUBIK
By the time I was 10, I could solve the Rubik’s cube in under a minute. I was fascinated by the popular puzzle since the day I Iaid my hands on it. I spent that entire day trying to solve one face side and by the end of the day when I finally managed to do so, I ran around the house ecstatically to show every single person my achievement. Within a month, I learnt all the algorithms and could solve the cube easily in under a minute. That was the beginning of my cubing journey.
Today, I average 20 seconds on the 3×3 Rubik’s cube. My collection of cubes adorn my desk and I love doing a few solves a day to keep in touch with this mind-stimulating activity. However, all said and done, speed cubing is simply all about the memorization and mastery of long and complex algorithms. But what really is the mathematics behind the famous Rubik’s cube?
I am inclined towards the mathematics side of everything and I was eager to dig deep and research about the math residing in this puzzle. I found the results extremely interesting and in this article I have attempted to share some of my findings. Rubik’s cube math is hard. In this article, I have tried to simplify and explain some of the mathematical concepts that surround the Rubik’s cube.
The Total Number of Possible Arrangements on the Rubik’s Cube
So many of you may have heard people talk about the immense number of ways the Rubik’s cube can be scrambled up. But how do we reach that number mathematically?
If we simply think about it, to find that number may seem daunting.
Let’s do some math.
Starting with all the corner pieces.
There are 8 corner pieces on the Rubik’s cube. So if we take these 8 corner pieces out, the total number of ways we can rearrange these back is 8! Ways
However, this is not all! 1 corner piece has 3 orientations, giving 38 possibilities for each permutation of the 8 corner pieces. So till here we have, 8! x 38
Similarly we move on to the edges. There are 12 edge pieces in total which can be arranged in 12! ways. Each edge piece has 2 possible orientations, so each permutation of edge pieces has 212 arrangement. So now we have, (12! x 212) (8! x38 )
The center pieces are fixed and therefore are unimportant in determining the possible number of ways the cube can be mixed up.
Now, you may think that this is the final number of possible arrangements, however this is not all there is.
In the Rubik’s cube, only 1/3 of the permutations have the rotations of the corner cube pieces correct. Only 1/2 of the permutations have the same edge-flipping orientation as the original cube, and the edge and corner pieces combined exhibit two cycle parity, and therefore only 1/2 of their arrangements would result in a solvable cube. This is important to note as even if we take one corner piece with the wrong rotation or one wrong rotation of the edge piece, it would not exist on the standard Rubik’s cube. An incorrect rotation would in fact give rise to a whole new universe of possible arrangements!
An example of a disoriented corner on the Rubik’s cube which would not exist on the standard cube.
So the number we finally have is-
That’s about 43 quintillion possible cases.
This number is about 100 times more than the number of seconds the universe has existed which is approximately 4.3 x 1017 seconds!
God’s Number and the Pigeonhole Inequality
Another important question that was raised by mathematicians was, if you could solve the cube from any position in the most efficient manner( the least number of moves), what would be the most possible number of moves you would have to make?
This number was referred to as “God’s Number” and intrigued many mathematicians.
Mathematicians in group theory (the theory used to solve the Rubik’s cube) formulated the pigeonhole inequality, which expresses the lower bound of this number, or in other words, it is not possible to be more efficient than this many turns.
So here is how we can understand it:
Since the first move can be made in any way, there are twelve moves you can make on the first turn (there are 6 faces, each of which can be rotated in 2 possible directions). But on each consecutive turn, you cannot make the move which undoes the last one. Therefore, each of the remaining turns can be done in only 11 ways. Therefore, the pigeonhole inequality translates to:
12 x 11n-1 > 4.3252 x 1019 which leads to the answer that n> 19.
(the number of possible outcomes of rearranging must be greater than or equal to the number of permutations of the cube)
Ever since the year 1981, group theory mathematicians began to try and find the exact value of God’s number. It took a long 30 years to finally find and confirm this number. In July 2010, thanks to the mighty computing power of modern computers(in the Google headquarters, San Francisco), the number was finally confirmed. Now, in order to confirm all 43 quintillion cases we would have to run code on every single case which would take forever. Luckily, working off of Lagrange’s theorem, mathematicians were able to crunch the number of positions they needed to analyse down to about 2 billion. Later, after an extensive proof, they were able to determine that the symmetry involved in a Rubik’s cube allowed them to cut the number of positions by a factor of 48. The remaining 56 million positions were able to be analysed by computers which were able to fix all 56 million of these positions in 20 moves or less. Thus, God’s number has officially been proven to be exactly 20.
This means that any of the 43 quintillion cases of the Rubik’s cube can be solved in 20 or less moves.
The Superflip Position
Superflip algorithm: U R2 F B R B2 R U2 L B2 R U’ D’ R2 F R’ L B2 U2 F2
In 1995, Michael Reid discovered the “superflip” position, and proved that this position took exactly 20 moves to solve when done the most efficiently. Basically, in this position all the edge pieces are flipped and all the corner pieces remain perfectly oriented. Since it is now proved that gods number is 20, it means that this is one of the 43 quintillion cases that requires 20 moves to solve(making it one of the hardest scrambles), when done most efficiently.
One special property of this case is that if the superflip algorithm is done twice, it takes you back to where you started!
The mathematical notation of the cube
The Rubik’s cube is associated with a certain notation, which assumes that you point one center at yourself and do not reposition the cube in the middle of the algorithm. The notations x, x’, y, y’, z, and z’ do refer to the rotation of the Rubik’s cube along one of its 3 axes, but are not commonly used. The following letters all represent the turning of one side of a Rubik’s cube: R(right) F(front) L(left) D(down) U(up) B(back) with a ‘ added after the letter to denote turning that side in the opposite direction. Ex: R’ is the inverse of R
These notations make it easier to describe moves and form algorithms.
Group Theory
In mathematics, the Rubik’s Cube can be described by Group Theory.
Group theory is the study of groups. A group is defined as a particular set of elements that when an operation is performed on two of the elements it results in a third element of the group and we tour axioms or rules. They are sets equipped with an operation (like multiplication, addition, or composition) that satisfy certain basic properties. A Rubik’s cube meets the guidelines to be considered a group. In the Rubik’s cube group, the elements are the 43 quintillion possible permutations the cube has and the operation taking place is the turning of the faces.
Axioms of Group Theory:
Axiom #1
Closure- This axiom says that the set of elements must have closure. This means that there is a predefined list of actions that can never change. The moves that can be performed on a Rubik’s cube are examples of the predefined actions.
Axiom #2
Associativity- This axiom states that the group must have associativity. This means that you could put parentheses wherever you want in the group operation and it would be equivalent to the same operation but with parentheses in a different place.
By using numbers, if we had the equation 1+2+1 and then we put a parentheses, making it 1+(2+1), they would still be equivalent.
Axiom #3
Identity-The third axiom is identity. Basically, there is an identity in the set that keeps the set unchanged. For example, if you do the moves R U and then do not turn anything and rotate the cube around in your hands, the cube will stay in the same position until you do another move. To understand this with numbers, if we add 0 to any number , the number value will not change and remain the same.
Axiom#4
Inverse- The final axiom is inverse. There must be an inverse for each element of the set. With numbers, for example, you can add 1+1 and the inverse will be 1-1. The same way an inverse exists to every move made on the Rubik’s cube. Say you made the moves R U F, the inverse to these will be reversing the order of the moves and also making the moves in the opposite direction, translating to F’ U’ R’.
These are the fundamentals behind the mathematics of the cube. Group theory mathematicians formulate algorithms to solve the cube.
Canonical Cycle Notation, Algorithms and Cayley Graphs
Canonical cycle notation is used by group theory mathematicians to describe the rotation of the cubes in the Rubik’s cube when sides are being turned.
For: (1)(234)
Element 1 stays in its place, while the elements in the second group all rotate one space to the right.
This will result in (423)
In order to evaluate any given canonical cycle, you must follow three steps:
1. Begin the cycle with the smallest number.
2. Complete the first cycle by following the movements of the objects through the permutation. Do this until you close the cycle.
3. If you have used up all the numbers, you are done. If not, return to step 1 to start a new cycle with the smallest unused element.
Through the use of Cayley graphs, which are complex graphs that encode the abstract structure of a group, group theory mathematicians were able to come up with building block algorithms.
For eg:
1. FUDLLUUDDRU (flips exactly one edge cube on the top face)
2. R’DRFD’ (twists one cube on a face)
Using canonical cycle notation, these basic algorithms are able to be converted to meet specific requirements. Each letter is replaced by a number, and is swapped in the same fashion.
Solving the Rubik’s Cube
Using group theory, mathematicians developed the CFOP method (Cross – F2L – OLL – PLL), sometimes known as the Fridrich method – the most popular method for solving a Rubik’s cube. The algorithms generated by group theory allow people to easily solve any scramble of the Rubik’s cube by breaking it up into steps. A common misconception is that you solve a Rubik’s cube by colours, transitioning from one to the next until all 6 are complete. But in reality, the Rubik’s cube is solved in its three layers, from the bottom up.
To conclude, the Rubik’s cube is a mathematician’s delight. There are numerous mathematical concepts at play at various levels – be it the construction, scrambling or the solving of this bestselling puzzle. Above are some of the key concepts that form the basis of its operations and each one is a subject of vast research for experts in the field of mathematics. An expert cuber benefits from the ingenuity of algorithms that are derived as a result of the mastery of this complex mathematics of cubing!
References:
https://web.mit.edu/sp.268/www/rubik.pdf
https://81018.com/universeclock/
https://math.stackexchange.com/questions/2968196/lower-bound-on-gods-number-in-the-rubiks-cube
https://www.youtube.com/watch?v=Aeuc4WYPnDQ
Comments are closed.