How to Solve a Rubik’s Cube Using Graph Theory
Since I was ten, I’ve been fascinated by the Rubik’s Cube. After solving it for the first time with the help of a YouTube tutorial, I worked to get as fast as I could — three years later I went to the World Championships in Las Vegas and later organized competitions of my own. My interest sputtered out over the next couple of years as I moved on to other hobbies, but now, seven years later, I found the cube again as I lay in my dorm after a graph theory lecture. In thinking of ways that a computational graph could be used in the real world, I realized that a Rubik’s Cube could be perfectly represented as a graph. In this graph each vertex is a state with edges connecting to each state that is reached by applying one turn. To implement this idea I chose to use a 2x2 Rubik’s Cube because it only has 3,674,160 positions as opposed to a 3x3’s 43,252,003,274,489,856,000, but the same idea would apply to any sized cube.
A cube has six sides and each side can be rotated 90º clockwise, 90º counterclockwise, or 180º (all of which count as one move in the cubing world) so each vertex will have exactly 18 neighbors (6 sides · 3 moves/side). To generate a graph of the cube that includes all possible positions:
- Start with a solved cube
- Apply each possible move, creating a set, S₁, of all states that are one move from solved. Add an edge between each of the these states and the solved cube.
- Repeat this process again for every state in S₁ to produce S₂, all states that are two moves from being solved. Keep in mind that some moves will simply undo the previous turn and solve the cube again… discard these states. Continue for S₃, S₄, etc… until you have a set where no turn produces a new state.
Now if we are given a scrambled cube, we can simply start with the solved cube and generate the graph using the method described above until we encounter the scrambled cube. Then we can backtrack along the edges to find the solution.
This method works, but in practice it just isn’t good enough. Worst case scenarios can take around 15 seconds to generate a solution, so we’ll have to get creative to optimize the process. The first inefficiency is that we are considering every orientation of every state.
There are 24 ways to orient a cube, so if we can find a way to get rid of the duplicates then we can drastically reduce the work we need to do. To solve this problem, we can lock one corner in place when generating the graph. By locking the corner in place, we still generate every possible state but in only one orientation.
This is good, but we can still do better. Right now we are generating the graph from the solved cube until we reach the scrambled state, but consider what would happen if we generated from both the solved AND scrambles states until the two met.
Searching from both the scrambled and solved states will allow us to generate fewer positions and still find a shortest path between the two states. If you don’t find this intuitive, consider the area of two small circles vs one large circle — in our case, the area of the two smaller circles will always be smaller than the larger one.
Aside from solving the cube, the graph theory approach uncovers a couple of interesting insights. After generating the entire graph, we can see the distribution of the number of moves it will take to solve every possible scramble.
In the cubing world, a statistic of particular interest is what’s called “God’s Number.” God’s Number describes the maximum number of moves needed to solve any scramble. Going into this project, I knew that God’s Number for a 3x3 is 20, but I had never considered what it would be for a 2x2, so finding the answer on my own was one of my main metrics for success. According to the results from my project, God’s Number for a 2x2 comes out to be 11, and upon validation with a quick Google search, this result is correct.
This article only covers part of the project — after implementing this, I added another component that can determine the state of a cube from a series of pictures using OpenCV. If/when I write part two, it will be linked here.
