Rubik’s Cube Optimization
Jordan Abbatiello, Adam Corbett, Shanade Beharry
Department of Computer Science
University of North Carolina Wilmington
Abstract- Produce the set of face-turns for any scrambled cube, which returns the cube to the completed state with the shortest set size. In order to accomplish this goal, we will first be designinga human oriented algorithm; creating an original implementation of Thistlethwaite’s algorithm, and analyzing Kociemba’s two-phase algorithm
Keywords—Rubik’s Cube, faces, cubies, facet, Kociemba, Thistlethwaite
I.Introduction
The Rubik’s cube was invented by Ernö Rubik in 1974 and was meant to be impossible to solve. It has been proven that there are roughly 43 quintillion permutations on a standard Rubik’s cube. However, many mathematicians and scientists strived to find a way to solve this cube in the least number of moves possible. Team 33 has challenged themselves to write an algorithm that can solve a Rubik’s cube with the shortest possible set size.
II.Formal Statement
A.The Goal
To produce the set of face-turns for any scrambled cube which returns the cube to its completed state with the least amount of moves.
B.Formal Definition
A Rubik’s cube is a twisty puzzle that is comprised of six sides each identified by nine colored faces or facets. Any piece with two or more facets is known as a cubie. Cubies with two facets are known as an edge piece and cubies with three facets are known as a corner piece. The face in the center of each of the six sides dictates the color for that side of the cube since any rotation around the center, or axis, will never alter the position of that face. Cube notation, or the list of moves applied to the cube, is generally referred to as up, down, front, back, left, and right where up, or U, are the faces on the top of the cube, down, or D, are the faces on the bottom of the cube, front, or F, are the faces on the front of the cube, back, or B, are the faces on the back of the cube, left, or L, are the faces are the cubes on the left of the cube, and right, or R, are the faces on the right side of the cube. Cube notation also refers to the degree of the rotation. A quarter rotation in cube notation, such as R or U, refers to a 90 degree clockwise turn of those sides. A half rotation, such as R2 or U2, refers to a 180 degree rotation of those sides. The Rubik’s cube problem will later describe a principle known as inverse. Every item in the cube notation has an inverse which is illustrated by a prime operator such as R’ or U’, which refers to a 90 degree counter clockwise rotation of the described sides.
Many mathematicians and scientists who have contributed to this problem have all come to the conclusion that the Rubik’s Cube problem can be modeled after a group theory problem. A group is defined as a set of elements when combined with a binary operator, known as the group law of G, to form another element. Keeping the focus on a Rubik’s cube, the elements relate directly to the faces on any given side of the cube and the binary operator is multiplication in this scenario. For a mathematical system to be considered a group theory problem, the system must satisfy four axioms: closure, associative, identity, and inverse.
Closure means that all group operations must be restricted to group elements. For example if a and b in group G, then a*b is also in group G. This is true for the Rubik’s cube where any operation performed on the group, in this case the faces of the Rubik’s cube, will result in a formation of faces identical to another element in the group.
The second axiom is associativity where the priority of moves produce the same element regardless of where the priority of moves resides. For example ifa, b,and cin G, then (a*b)*c = a*(b*c).The Rubik’s cube satisfies this axiom and can be observed by simply rotating the cube and comparing the faces.
The third axiom is identity, where there is an operation, when applied to an element in the group, results in the element. Shown by a*e = e*a = awhere e is the identity operation.For a Rubik’s cube, this is simply a null operation, or zero rotations applied to the elements.
The final axiom is inverse. The axiom states that every element has an inverse operation when applied to an element in the group will produce the identity of the group. Shown by any element a in G, if a*a-1=ewhere a-1 is the inverse operation.
Each rotation of a face and the cube is considered a permutation of the position and orientation of the sub cubes. The groups created are known as permutation groups which simply provide a way to map something onto itself. Together, the rotations create a generating set which then creates a group by composition of the rotations.
III.Context
Contributors
In 1981, Morwen B. Thistlethwaite, a knot theorist and professor of mathematics, created an algorithm, using group theory that can solve the Rubik’s cube in much less moves than a human. In his case, fifty-two was the lowest he managed in his implementation on lower ram systems, however, full implementations have been proven to be forty-five moves or less. The algorithm is comprised of four stages that use large lookup tables for all the coordinates of effected elements in each stage. Stage one fixes the orientation of the edges. Stage two fixes the orientation of corners and places the middle layer edges into their slice. Stage three ensures that the corners are placed in its correct tetrads and that the edge parity is now made even. The final phase four fixes the final position of the edges and corners.
In 1992, Herbert Kociemba, a German teacher of mathematics and physics, improved on Thistlethwaite’s fifty-two move algorithm by cutting it down to twenty moves or less. He merged the first two and last two phases of Thistlethwaite's together. In this much larger space he uses a search algorithm called iterative deepening IDA* with a lower bound heuristic function. Kociemba’s algorithm comprises of two complex stages that uses even larger lookup tables for all positions in each phase. Phase one uses two coordinates and both table generation and lookup to find moves to the next phase. The heuristic function estimates the number of moves necessary to reach the solved state and will prune any branch that reaches over a certain length. Phase one solves the orientations of corners and edges and the edges of the UD-slice are moved to their slice. Phase two uses similar systems to restore the permutation of the corners and edges. The algorithm is also set up to continue searching for shorter possible solutions by going into phase two from suboptimal solutions from phase one. This algorithm was used to prove that God's number, the maximum number of required moves from any state to solved, for a Rubik's cube is twenty moves.
IV.Experimental Procedure
The experiment that was ran compared three different algorithms, the beginner's method, Kociemba's, and Thistlethwaite's. We used Kociemba's official package as a base line for the currently best known algorithm. We implemented a version of Thistlethwaite's algorithm. We also designed and implemented the beginner's algorithms.
For the design aspect of the project, we designed an algorithm based on the tactics in which a human would solve a Rubik’s cube. For this method, it is broken into seven stages where once a stage has been completed, if restricted to a certain sequence of moves, the previous stages will not be disrupted. For example, if the white cross is completed, every stage following will move the target cubies into their final positions without disrupting the initial white cross. The stages are to solve the white cross, white corners and first layer, second layer, top cross, top edges, position of corners, and then finally the orientation of the corners. The algorithm we created uses a two-tier integer array where the first tier represents the color of the side and the second represents the position of that face on its respective side. Essentially the program creates a scrambled cube, runs that scrambled cube through a series of if-else statements that check the positions of target cubies (cubes that are involved in each of the stages) and applies several rotations to move them into their desired position.
Thistlethwaite's algorithm uses group theory to slowly move the cube through several subgroups until it is in a group with only one state, solved. The largest group contains all possible cubes. From this group the orientation of the edges is fixed using any combination of moves. This moves it into the subgroup G1. Once in G1, if the U and D faces are restricted to only halve turns, the cube can never leave the G1 subgroup. Phase two moves the cube into G2 by fixing corner orientation and moving the middle layer edges into their slice. Similar to G1, once in the subgroup G2 the cube cannot leave if some moves are restricted. In this case it's U, D, F, and B allowing only halve turns. The next group, G3, is achieved by fixing the edge parity and places the corners into their proper tetrad and all edges into their slices. This group can't be left if all the turns are limited to halve turns. The final subgroup, G4, is the solved cube. While our implementation did not fully work, enough was implemented that we could confidently fill in the few holes in our knowledge that we believe based on what we have seen from our implementation
Kociemba's algorithm uses a similar idea to Thistlethwaite's. However, while it relies much on group theory for the formulation of the groups, it also uses state space searches for much of the algorithm. The groups in this algorithm are based on combining Thistlethaite's. The first group is combination of G1 and G2. The second group is a combination of G3 and G4. This combination makes the state space for Kociemba much larger than Thistlethwaite and is too large to be stored in tables. Kociemba then uses partial lookup tables generated while looking through the space to help speed up sequential searches. The state space is searched using iterative deepening with a heuristic function, or IDA*. IDA* works by doing a breadth first search while checking expected branch length against a maximum heuristic. The expected branch length is current length plus estimated distance from the next group. If this total is higher than the max length of the current phase the branch is pruned. This branch is also added to the pruning table and if seen again, immediately pruned.
The algorithms were then ran on one thousand random cubes. Cubes were generated from a solved cube and had thirty random moves applied to them. Thirty random moves is competition standard for a scramble. Each algorithm had its runtime, ram usage, and max, min, and average of its solution length measured.
V.Results
The beginner’s method ran very smoothly and it used up only forty-five MB of RAM. The Maximum amount of moves it took before it was solved was two hundred and seventy-four, the minimum amount of moves was one hundred and three and the average amount of moves was one hundred and eighty three; all had the Rubik’s solved in less than one millisecond.
Our implementation of Thistlethwaite’s algorithm used 1.5GB of RAM, the maximum amount of moves were forty-five and the average being thirty-five. The lookup table took approximately thirty seconds to generate and then the Rubik’s Cube was solved in less than three milliseconds.
Kociemba’s algorithm used 150MB of RAM, the maximum amount of moves were twenty and the average being eighteen or nineteen. It took 1,750milliseconds for the first Rubik’s cube solve because of the lookup table generation. All solves afterwards too between five to two hundred milliseconds.
VI.Interpretation and Conclusions
From the experimental phase, it’s clear that the beginner’s method is the fastest and uses the smallest amount of memory. These two factors, even in combination, do not outweigh the set size of Kociemba’s algorithm. The goal of the experiment was run three different algorithms in order to find the smallest set size and Kociemba’s algorithm produced that result consistently. Thisthlethwaites algorithm fell inbetween these two algorithms in terms of set size, but exceeded the RAM requrements greatly. The run time after the tables were generated could be considered efficient and therefore we would rank Thisthlethwaite’s algorithm second to Kociemba’s.
After analyzing the Rubik’s cube problem, we found that there are numerous similarities between this system and dynamic programming. If you were to look at Kociemba’s source code for his cube solver, the coding itself is rather compact and the difficulty resides in understanding the problem itself. Based on this information, we can conclude that this problem is an example of dynamic programming.
VII.Future Work
Moving forward there are several improvements that we would have liked to implement. The first being Korf’s algorithm. While we were researching, we found that Korf’s algorithm will give you the shortest set of moves indefinitely, but its runtime is maximum runtime has never been proven. In the future, we would have like to compare his results, RAM usage, and runtime, against the algorithms described in our project. For the beginner’s method, we would also have liked to allow for user input where a user could enter their own cube into the program and it would print out a set of moves to that would result in a solved cube. In terms of cube representation, the beginner’s method uses colors rather than standard cube notation, and in the future, we would like to make the transition into cube notation. Finally, we unanimously agree that a complete implementation of Thisthlethwaite’s algorithm would have benefited the data for this project. We would rework this phase in the future.
VIII.Questions
1)Which Algorithm was the best?
Kociemba’s Two-Phase Algorithm.
2)What is the problem type for a Rubik’s cube?
Group Theory
3)What search method does Kociemba use?
IDA*
4)How many phases are in Thistlethwaite’s Algorithm?
Four
5)What are the four axioms that must satisfied in order to qualify as group theory problem?
Closure, Associativity, Identity, Inverse.
References
[1]Kociemba, Herbert. "Solve Rubik's Cube with Cube Explorer."Solve Rubik's Cube with Cube Explorer. N.p., 2014. Web. 26 Apr. 2016.
[2]Scherphuis, Jaap. "Jaap's Puzzle Page." Rubik's Cube 3x3x3. N.p., n.d. Web. 26 Apr. 2016.
[3]Tucker, Megan. "Group Theory Cubed." YouTube. N.p., 06 Jan. 2014. Web. 26 Apr. 2016.