2 - Mathematics of a Rubik Cube

This section delves into how mathematics dictates the optimal ways to solve the Rubik Cube. This section, will be one of the hardest to understand at face value and a rooting in mathematics will definitely aid in understanding the intricacies. However, a 'human' explanation will be provided so even a novice should be able to come away with some understanding.

Terminology:

Initial State = The random initial scramble of the Rubik's Cube.

Lower Bound Heuristic = An heuristic function that will continually search for the lowest amount of a specified variable (in this case it will search for the lowest amount of moves).

IDA* = Iterative deepening A* is a path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes.

ARCS = Autonomous Rubik Cube Solvers.

1.0 - Group Theory and God's Number

The Rubik Cube has a plethora of solving algorithms, which can be categorised by human methods (doable by a human) and computational methods (only achievable by a computer). It is of no surprise; computational approaches provide the most optimal solution due to their sheer processing power. This is demonstrated as human methods (Heise, 2017; Zborowski, 2021) on average, require considerably more (~20-40) moves than that of the computational methods (Grol, 2010; Rockicki et al, 2010; ‌ Korf, 1997).

The most popular computational methods are deeply rooted within group theory as it allows for subsets of the whole problem to be pre-computed and called upon from a given initial state (Korf, 1997). The Rubik cube group, Gc, is subject to all its possible rotations (U, F, R, L, B, D) in that the cube can only be manipulated into another state using such moves (Joyner, 1997), shown in Equation 1.

Gc= (U, F, R, L, B, D)

Equation 1 – Rubik Cube Group

Through 30 years of supercomputer processing, the maximum amount of moves needed to solve a cube was discovered to be 20 (Rockicki et al., 2010). Where the metric of a move is either a 90 or 180 degree turn clockwise or anti-clockwise. This value was coined ‘God’s Number’ as only a deity could consistently solve the cube in under 20 moves. It serves as a standard to compare other algorithm’s effectiveness against when deliberating the optimality of a solution.

1.1 - History of Computational Algorithms and Their Application

Morwen Thistlewaite in 1981, used group theory to divide the problem into four nested subgroups (Equation 2 – Equation 6). Where g4 is the solved state and G0 = Gc (Equation 1). The method was to take the cube from G0 (Equation 2) to G4 (Equation 6) by only using the constraining moves within group Gi-1, leading to a reduction in possible states as the groups are ascended (El-Sourani, Hauke and Borschbach, 2010). This, in turn makes the number of possible states a lot more manageable. However, the upper bound of this algorithm was shown to require 52 moves (Grol, 2010) which is far from an optimal solution.

G0= (U, F, R, L, B, D)

Equation 2 – Thistlewaite’s Group G0

G1= (U², D², L, R, F,B)

Equation 3 – Thistlewaite’s Group G1

G2= (U², D², F²,B², L, R)

Equation 4 – Thistlewaite’s Group G2

G3= (U², D², F²,B², L², R²)

Equation 5 – Thistlewaite’s Group G3

G4= (1)

Equation 6 – Thistlewaite’s Group G4

Herbert Kociembas in 1992 presented his ‘two phase’ approach. Directly improving upon Thistlewaite’s work, by combining two of Thistlewaite’s groups (Scherphuis, 1999). From G0 to G1 the right coset space was used to solve the cube sub-optimally but from G1 to G2 iterative deepening A* (IDA*) with a lower bound heuristic function found the optimal solution (Kociemba, 2020). The three groups can be seen in Equation 7 - 9. Rockicki et al (2010) later proved the solution required at most 21 moves and 18 moves were needed on average to solve the cube (Kociemba, 2020).

G0= (U, F, R, L, B, D)

Equation 7 – Kociemba Group G0

G1= (F²,B², L², R², U, D,)

Equation 8 – Kociemba Group G1

G2= (1)

Equation 9 – Kociemba Group G2

This halved the upper bound of Thistlewaite’s algorithm, making the solution considerably faster and being a mere move more than that of Gods number. Several autonomous Rubik Cube solvers (ARCS) have implemented the algorithm for that reason (Grönås and Mazur, 2020; Barucija et al., 2020) including even that of the current Guinness world record holder (Swatman, 2017).

Richard Korf in 1997 presented an approach, which used IDA* (alike Kociembas) with a lower bound heuristic, but for the whole problem. This was solely reliant upon large look-up tables (‌Korf, 1997) and always produces optimal solutions at or below Gods number. This idea was originally proposed by Culberson and Schaeffer (1996). But takes considerably longer to produce than that of Thistlewaite’s or Kociembas solutions; in turn, taking longer to solve a cube within an ARCS. With Kaur (2015) stating that beyond a depth of 9 moves to solve, Thistlewaite’s solved a cube faster than that of Korf’s, and Hoang (2015) displaying that Kociembas algorithm required only up to 5 more moves at most for 17+ move states.

1.2 - The Human Explanation

At a first glance, group theory can be a lot to understand. But in relation to a Rubik Cube, it breaks the solution into several intermediate steps (groups), in which the next step can only be reached by using the moves within the current group. As each group in transcended, the number of potential cube states is reduced, taking the user closer to a solution and reducing the computational time needed to reach a solution.

The algorithm implemented within this project is Kociemba's algorithm. The reasoning behind using Kociembas over Korf's, is that Kociembas finds near-optimal solutions in a fraction of a second, whereas Korfs will find the actual optimal solution over several hours. Alas, this would make the Rubik Cube solving robot significantly less entertaining if you had to wait 2 hours for it solve. The next article will focus upon what systems already exist to autonomously solve a Rubik Cube, as in the words of Picasso:

Good artist copy, great artists steal.

Disclaimer: we will not be stealing robots, however, we will be taking inspiration from some of the best parts of other projects and improving upon them.

References

Barucija, E. et al (2020) ‘Two Approaches in Solving Rubik’s Cube with Hardware-Software Co-Design’, 2020 43rd International Convention on Information, Communication and Electronic Technology (MIPRO), pp. 128-133. DOI: 10.23919/MIPRO48935.2020.9245201.

Culberson, J.C. and Schaeffer, J. (1996) ‘Searching with Pattern Databases’, Conference of the Canadian Society for Computational Studies of Intelligence, vol 1081, pp. 402-416. DOI: 10.1007/3-540-61291-2_68.

El-Sourani, N., Hauke, S. and Borschbach, M. (2010) ‘An Evolutionary Approach for Solving the Rubik’s Cube Incorporating Exact Methods’, Applications of Evolutionary Computation, EvoApplicatons 2010: EvoCOMPLEX, EvoGAMES, EvoIASP, EvoINTELLIGENCE, EvoNUM, and EvoSTOC, pp. 80-89. DOI: 10.1007/978-3-642-12239-2_9.

Grol, R.V. (2010) ‘The Quest for God’s Number’, Math Horizons, 18(2), pp. 10-13. DOI: 10.4169/194762110X535961.

Grönås, D. and Mazur. F. (2020) Robotic Cuber. Undergraduate Thesis. KTH Royal Institute of Technology. Available at: https://www.diva-portal.org/smash/get/diva2:1462066/FULLTEXT01.pdf

Heise, R. (2017) Human Thistlewaite Algorithm. Available at: https://www.ryanheise.com/cube/human_thistlethwaite_algorithm.html

Hoang, L.T. (2015) Optimally Solving a Rubik’s Cube Using Vision and Robotics. Master’s Thesis. Imperial College London. Available at: https://www.doc.ic.ac.uk/teaching/distinguished-projects/2015/l.hoang.pdf

Joyner, D. (2009) Adventures in Group Theory: Rubik’s Cube, Merlin’s Machine, and Other Mathematical Toys. 2nd edn. Baltimore: John Hopkins University Press.

Joyner, W.D. (1997) Mathematics of the Rubik’s cube. Available at: https://www.fuw.edu.pl/~konieczn/RubikCube.pdf

Kaur, H. (2015) Algorithms for Solving the Rubik’s Cube. Master’s Thesis. KTH Royal Institute of Technology. Available at: https://www.diva-portal.org/smash/get/diva2:816583/FULLTEXT01.pdf

Kociemba, H. (2020) The Mathematics Behind Cube Explorer. Available at: http://kociemba.org/cube.htm (Accessed: 4th November 2020)

Korf, R.E. (1997) ‘Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases’, AAAI-97, pp. 700-705. Available at: https://www.aaai.org/Papers/AAAI/1997/AAAI97-109.pdf.

Rockicki, T. et al (2010) God’s Number is 20. Available at: http://cube20.org/

Scherphuis, J. (1999) Jaap’s Puzzle Page. Available at: https://www.jaapsch.net/puzzles/compcube.htm#kocal

Swatman, R. (2017) Fastest Robot to Solve a Puzzle Cube. Available at: https://bit.ly/32tfH9A

Zborowski, Z. (2021) ZZ speedcubing system. Available at: https://web.archive.org/web/20080612111837/http://www.speedcubing.com.pl/nooks_zz.htm