AbstractEver since the introduction of the Rubik’s cube, our goal as a society has been to devise ways to solve the cube faster. With advancements in algorithms, the maximum number of moves required to solve any cube in any scrambled position has been lowered to 20. This number is also known as the God’s number.

The aim of this paper is to explore how God’s number was identified and to elucidate characteristics of optimally solved Rubik’s cubes. In order to do so, 100,000 optimally solved Rubik’s cubes were analyzed. It was uncovered that a vast majority of the scrambled Rubik’s cubes required 18 face turn moves to solve. Future investigations should look into optimizing the number of quarter turn moves required to solve a Rubik’s cube in order to identify the most efficient way to solve a Rubik’s cube.

Introduction Over 350 million Rubik’s cubes have been sold to customers to date. Often regarded as the world’s best selling toy, the Rubik’s cube has been a craze among children, adults, and even mathematicians. While many of our goals might be to completely solve the cube, researchers have already passed that stage and are looking for methods to solve the cube in the most efficient manner (Joyner, 2008). Singmaster Notation Singmaster notation will be used throughout this paper to denote cube moves. It consists of the following commands: Table 1 – Cube notations are presentedFFront face rotated clockwise 1 quarter turnBBack face rotated clockwise 1 quarter turnLLeft face rotated clockwise 1 quarter turnRRight face rotated clockwise 1 quarter turnUTop face rotated clockwise 1 quarter turnDBottom face rotated clockwise 1 quarter turnThe inverse of these commands are as follows: Table 2 – Inverse notations and functionsF’Front face rotated counter-clockwise 1 quarter turnB’Back face rotated counter-clockwise 1 quarter turnL’Left face rotated counter-clockwise 1 quarter turnR’Right face rotated counter-clockwise 1 quarter turnU’Top face rotated counterclockwise 1 quarter turnD’Bottom face rotated counter-clockwise 1 quarter turnHalf turns are denoted by appending a “2” after the desired command. For example, a half turn of the bottom face is written as “D2.” Changes in orientation of the cube are denoted by X, Y, and Z. X represents a 90-degree rotation forwards, Y indicates a 90-degree rotation to the left, and Z indicates a 90-degree turn clockwise (Joyner, 2008; Campbell, n.

d.). Half turn and inverse rules apply for changes in orientation as well. X ROTATION Y ROTATION Z ROTATIONFigure 1. A visual on notations for changes in orientation (“Rubik’s Cube Notation – How to read the rotation letters”, n.

d.).Cube Dynamics There are 43 quintillion different possible combinations a Rubik’s cube can be transformed to. While daunting at first, the Rubik’s cube can be solved by following established algorithms and some intuition. Different series of algorithms are used based on the user’s proficiency with the cube. Beginner’s method.

The beginner’s method mainly consists of solving the cube layer by layer. With defined algorithms existing for the different scenarios possible, it often isn’t hard for someone to learn how to solve a cube. Advance methods. Advance methods require a deeper understanding of cube dynamics. The goal is to complete multiple tasks with fewer algorithms. Speed cubers today have achieved miraculous feats. Just recently, Mats Valk broke the record for solving a 3X3 cube with his time of 4.74 seconds (Weller, n.

d.)! However, human solvers are a lot less efficient than computers. Algorithms developed on computers can solve the cube in significantly fewer moves. In the field, the common goal has been to reduce the maximum amount of moves required to solve a Rubik’s cube.God’s Number In recent years, a dilemma that has eluded researchers for over 35 years was answered. The dilemma has allowed researchers to establish the maximum amount of moves, defined as any twist of a face, required to solve a cube in any scrambled position (Rokicki, Kociemba, Davidson, & Dethridge, 2013).

Upper and Lower Bounds Throughout the Rubik’s cube history, upper and lower bounds to the God’s number have been set by a number of researchers. Lower bound. The first lower bound was established rather intuitively using a counting method in 1980. The number of possible cube positions is greater than the number of distinct algorithms of 17 moves or less.

The aforementioned observation led researchers to believe that God’s number had to be at least 18 moves. In 1995, the lower bound changed due to the discovery of the solution to the superflip scramble. The superflip is a position where all corners are solved and all edges are flipped in their original position (Rokicki, Kociemba, Davidson, & Dethridge, 2013). Figure 2. A representation of the “superflip” cube positionIn 1995, Michael Reid uncovered that the superflip can only be solved in 20 face moves, thereby raising the lower bound of the God’s number to 20.

The superflip was the first scramble position identified that was solved in 20 moves. The solution is as follows (“M-symmetric Positions,” 2005; Rokicki, Kociemba, Davidson, & Dethridge, 2013):U R2 F B R B2 R U2 L B2 R U’ D’ R2 F D2 B2 U2 R’ LSince the aforementioned discovery, researchers have been aiming to essentially reduce the difference between upper and lower bounds. The ultimate goal was to obtain a difference of 0. Upper bound.

The upper bound of God’s number has changed drastically over the past 37 years. In 1981, Morwen Thistlethwaite identified the upper bound as 52. Almost a decade later, the upper bound was lowered to 42 by Hans Kloosterman (1990).

The upper bound was further lowered to 39 by Michael Reid in 1992 and to 37 by Dik Winter a day later. In 1995, Michael Reid raised the lower bound to 20 and lowered the upper bound to 29. The next breakthrough came 10 years later with Silviu Radu’s bound of 28, which he beat a year later with an upper bound of 27. Since then, Tomas Rokicki and his peers have lowered the upper bound all the way to twenty, thereby establishing God’s number (Rokicki, Kociemba, Davidson, & Dethridge, 2013).

Important Algorithms Thistlethwaite’s Algorithm. Thistlethwaite’s algorithm is based on group theory. Thistlethwaite divided the Rubik’s cube group (a group of all possible moves that can be performed) into restricted subgroups. Each subgroup has a goal in what needs to be accomplished. The transition between each phase completed only using moves in the preceding restricted subgroup. The restricted subgroups are as follows: G0 = {U, F, R, D, B, L} 7 MOVES G1 = {U, F2, R, D, B2, L}10 MOVES G2 = {U, F2, R2, D, B2, L2} 13 MOVES G3 = {U2, F2, R2, D2, B2, L2} 15 MOVES G4 = {1} – Solved Cube Upon optimization, it has been established that the algorithm can solve any jumbled cube in 45 moves or less (“Progressive Improvements,” n.

d.). Kociemba’s algorithm. Kociemba’s algorithm is an improvement on Thistlethwaite’s algorithm. The algorithm only has 2 restricted intermediary subgroups namely:G0 = {U, D, L, R, F, B}12 MOVESG1={U, D, L2, R2, F2, B2}18 MOVESG2={1} – Solved Cube The rules of the Thistlethwaite’s algorithm apply here as well. Together, these algorithms helped researchers discover the God’s number. All of the possible cube positions (43,252,003,274,489,856,000) can be solved with 20 moves or less. Constant improvements to the algorithms aid researchers in identifying optimal solutions (lowest number of moves) for Rubik’s cube positions (“Progressive Improvements,” n.

d.). Optimal Solutions Distribution The cube explorer software can be used to optimally solve Rubik’s cubes from any shuffled position. The number of moves taken is always 20 or below.

The software has enabled people to develop new personal algorithms and identify optimally solved cubes (Kociemba, 2017). The optimal solve length has a wide range of number of moves. To characterize optimal solve length statistics, an open source file with 100,000 optimally solved Rubik’s cubes were obtained (Kociemba, 2017). Table 3 breaks down the 100,000 cube solves based on the number of moves taken to optimally solve each cube.Table 3 – The breakdown of the 100,000 cubes optimally solved.

Number of Moves for Optimal SolveFrequency (number of cubes)14181519716271017266731867099193303200 As seen in Table 3, most solves were completed in 18 moves. The distribution is graphed in figure 4 below. Figure 4. A representation of the distribution of the breakdown of 100,000 cubes optimally solved. Table 4 lists measures of central tendency values for the distribution presented in Table 3 and Figure 4. Table 4 – Basic measure of central tendency statistics on the presented distributionMean17.

7055Median18Mode18Standard Deviation0.5848Kurtosis2.1338Variance0.342 The average number of moves required to optimally solve the cubes was 17.7055. Most optimally solved cubes required 18 moves, while there were no cubes that required 20 moves. The above distribution is consistent with previous findings (Kociemba, 2017). Let us elucidate the probability of being presented with a cube shuffle that requires 14, 15, 16, 17, 18, or 19 moves to solve.

Table 5 – Probability of being presented with a shuffle that requires 14-19 moves to solveNUMBER OF MOVESPROBABILITY140.00018150.00197160.0271170.26673180.67099190.

03303 It isn’t a surprise that a cube with an optimal solve of 18 moves was most probable to be presented to you. Furthermore, the lack of any cubes that required 20 moves to solve can be attributed to the fact that only a handful of symmetrical shuffle sequences have been identified to require 20 moves (Rokicki, Kociemba, Davidson, & Dethridge, 2013; Kociemba, 2017).ConclusionThe presented statistics help answer questions surrounding the Rubik’s cube since its invention. Through this investigation, it has been established that a majority of shuffled Rubik’s cubes require 18 moves to optimally solve them.

Future Studies While this study used the number of face turns (each rotation of the cube is considered a move), studies should look to identify the God’s Number using quarter turns (each quarter turn is considered a move). Optimally solved cubes based on face turns might not be optimal when looking at it from a quarter turn perspective. Therefore, it is important to optimize in quarter turns as well as face turns in order to identify the most efficient way to solve a Rubik’s cube.