Use 3 or 4 of the mathematical/computational methods explored in the class to find solutions to Rubik's Cube .
Rubik’s cube is a 3x3x3 cube, composed of 26 smaller cubes arranged in over the six face planes of the bigger cube. Each face has a unique color and can rotate freely, allowing in overall 18 different moves. The cube can be seen as a finite state machine, with 901,083,404,981,813,616 possible solutions, as demonstrated by Turner and Gold in 1985, using Burnside’s lemma. Many possible short solutions have been proposed, however none has achieved the limit proposed by Berlekamp et al of 18 moves.
The solutions tent to fall in to general camps. Some generalized solutions, formulate the problem in term of permutation groups, proposing planning algorithms that search efficiently over large groups of maneuvers (sequences of permutations). The other approaches are based on heuristics, usually solving for sub-sections of the cube using graph search algorithms like A*. Of this group, on of the most accepted solutions is the one proposed by Kociemba. Using a two phase algorithm, the solution first solves a small subgroup, using A* search. The second part solves the remaining subgroup, using a set of known maneuvers, searching over the permutation space.
I am interested in this problem as a test-ground for the different techniques we learn during the course of this class. For this final project, I tried formulating the problem from different perspectives. However, due the sheer size of the cube states spaces frustrated my first attempts. I decided to reduce the problem to the 2x2x2 cube pictured here:
The pocket cube has a reduced space, with only 3674160 different states, making brute force solutions possible. The cube still shares enough similarities with its big brother to be interesting. There are 12 possible movements at every moment, 2 per each face. To simplify even more the problem, I only consider quarter face rotations, ignoring whole cube movements.
My first attempts were based on search algorithms like A*, which require a heuristic distance to the complete solution. I didn’t found using A* very interesting, since it has been widely used in similar problems with well known results. However, finding a heuristic measurement sound promising, and eventually lead to the proposed solution. Other different types of formulations will be briefly described at the end of this document.
How do we know how close we are to the solution? Following my experience with A* I decided to create a measurement of how close is certain state of the cube from being solve. The proposed approach goes as follows: Divide the cube in its 8 constituent smaller cubes. Face rotations are position permutations over the matrix of sub-cubes and color permutations over each individual sub-cube. For each sub-cube, find all the possible states (position and color permutations) corresponding to each face rotation and can make a graph of these states. Using that graph, is possible to find the distance of each sub-cube state to it’s solve state, using algorithm like Dijkstra. The sum of all the sub-cube distances corresponds to our heuristic distance. The state graph for every sub-cube is identical, and can be seen below:
To test the heuristic, I decided to use Simulated Annealing. Here the heuristic becomes the energy function to be minimized. Additionally, I added a bounding matrix, in which the energy was reduced when sub-cubes that are neighbors in the solved state, end up next to each other after a rotation. The application was written in java, and can be seen here:
The results weren’t very encouraging. Without the bonding matrix, the application was unable to solve any cube out of 1000 randomly generated. However, after the bonding matrix was added, it was able to solve 11, which is (I think) better than just random. The length of the solutions ranged from 50 to 500 moves.
Berlekamp, E.R., Conway, J.H. and Guy, R.K., Winning Ways, Academic Press, London, 1981.
Fiat,A., Moses,S.,Shamir,A.,Shimshoni,I. and Tardos,G.,"Planning and Learning in Permutation Groups", Proceedings of the 30th A.C.M. Foundations of Computer Science (FOCS) 1989, pp. 274-279.
Hofstadter, D.R. "Metamagical Themas: The Magic Cube's Cubies are Twiddled by Cubists and Solved by Cubemeisters." Sci. Amer. 244, 20-39, Mar. 1981.
Larson, M.E. "Rubik's Revenge: The Group Theoretical Solution." Amer. Math. Monthly 92, 381-390, 1985.
Turner, E.C. and Gold, K.F. "Rubik's Groups." Amer. Math. Monthly 92, 617-629, 1985.
Weisstein, E.W. . "Rubik's Cube." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RubiksCube.html