The story of how I solved 2x2x2 Rubik's Cube with a Python script
Its been a long time since I solved this problem, I was lazy to blog this amazing episode. When you read the title don’t think that I am a wizard, actually I used to claim that I was a Vampire but whatever works for you is fine. I am going to break the secret, I have been taking a MOOC on Introduction to Algorithms from MIT OpenCourseWare. Solving Rubik’s cube was an assignment problem for the lecture on graph search algorithms. I was provided with the abstraction of Rubik’s cube and I used breadth first traversal algorithm to find the shortest path to the solved state by generating a tree on the flow.
The whole Rubik’s cube is represented as a permutation of 24 numbers. If the cube is scrambled then the order of the permutation will be scrambled some thing like this [6, 7, 8, 20, 18, 19, 3, 4, 5, 16, 17, 15, 0, 1, 2, 14, 12, 13, 10, 11, 9, 21, 22, 23]. In solved state the permutation will look like this [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23] . We essentially assign a number to each box, it is a permutation of twenty-four numbers because there are twenty four boxes on the 2x2x2 Rubik’s cube. We are allowed to apply six operations on the cube which is a quarter-twist and the operation will produce a new permutation. We apply each of those six operations on the start state as a result we will get six new permutations and then again we apply those six operations on those six new permutations and we keep going. The size of the tree will increase exponentially. At some point we will get the solved state. Now that we have generated a tree we can find the shortest path from the solved state to the initial state with our parent pointers.
The code is available on GitHub. It was not until recently that I bought an actual cube and I solved it with the output of my Python script. The execution of this script takes a minute or two and it consumes a lot of RAM. The script can be optimized by making a two-way breadth first traversal both from the start state and the end state and meet somewhere in the middle (this was a part of the specification of the problem). This would reduce the memory consumption and make the script to execute in seconds. That seems like a trivial problem to me so I did not make that optimization. If you have time try to send me a pull request on GitHub making this optimization or else I might make this optimization some day.