Rubiks Cube Solver
Building a Rubiks Cube Solver With Python 3
Hi everyone, today we’re going to create a Rubik’s cube solver using python 3. In this blog post, I will be going through the game theory and algorithms needed so that you can beat any Rubik’s cube with ease.
With the popularity of Rubik’s cubes, I’m sure you’ve seen one before, but just in case you haven’t, I’m going to give a quick rundown of what they are. Rubik’s cubes are a popular game invented by Ernő Rubik. The Rubik’s cube has a simple set of rules, unscramble the scrambled 3-D puzzle. Traditionally, a Rubik’s cube is a 3x3 cube, but there are now many variations of the classic game.
Rubik’s cubes are complicated puzzles to solve with a total of 43,252,003,274,489,856,000 possible combinations.
Because of this complexity, many study Rubik’s cubes, ranging from hobbyists to mathematicians. Mathematicians have taken a liking to the cube due to its complex group theory, spawning many scientific papers on the topic.
One paper of great significance is the paper “The diameter of the Rubik’s cube group is twenty.” In this paper, they determined that “God’s Number” is 20 turns. “God’s Number” is a term with Rubik’s cubes that refers to the maximum number of turns to solve a cube in any configuration.
Another impressive thing that has come out of this studying is a variety of standardized algorithms for solving the cube.
Building The Cube
Okay, so now that we have background knowledge of the Rubik’s cube, our first step will be to build one. For the sake of simplicity, we’ll stick to nxn cubes so that we do not need to deal with the geometry of any other 3-D shapes (sometimes the puzzle is other shapes like squares or triangles).
To build our cube, let’s create a custom class for the user to interact. This way, we can store internal states in our cube object to reduce the number of variables needing to be passed to each function when manipulating the cube.
First, we’ll need to determine the most effective data structure for creating our cube. For the sake of this project, we’re going to use a three-dimensional array (nested list). I’ve chosen this data structure due to the needed manipulation of the cube. Using a three-dimensional array, we can create mappings to switch the squares in place on average in O(n) time.
Next, we need to build three separate functions for manipulating the cube. With a Rubik’s cube, there are only three types of possible moves you can perform.
Our three-movement functions all take a very similar approach. We use mappings to switch the position of the cubes in place. For the vertical and side twist function, we use a for loop to go through every row of the column making these functions have a time complexity of O(n). However, the horizontal twist function switches the rows in place, giving it a time complexity of O(1). We also check if we need to rotate the closest face with every rotation. To rotate a Rubik’s cube’s face, we transpose the respective matrix.
Solving The Cube
Now that we have a working model of the Rubiks cube, let’s start working on making the solver.
For a solver, there are multiple approaches we could take to solve this. However, we’re going to take a game tree approach.
With the game tree approach, we know that we are going to need to search the game tree to find the least moves possible to solve the cube. We could use a brute force approach however, with today’s computation limitations this is infeasible. Instead, we’re going to use a more efficient search algorithm.
The algorithm we’re going to use is the Iterative Deepening A* (IDA*) search algorithm. This algorithm is preferred over A* due to memory limitations. A* and IDA* use a similar approach where A* remembers which nodes were visited while IDA* does not. Typically A* is optimal for a search problem however, with such a large search space it is very likely we will run out of memory if we were using A*.
IDA* is a tree search method that uses a combination of heuristics and depth-first search (DFS). In IDA* the heuristics guide the DFS with the tree expanding every iteration similarly to Monte Carlo Tree Search (see my blog post Building a Chess Engine: Part 2 for an explanation of MCTS).
Below is an example tree for the IDA* method. In this diagram, I show the g_score (the cost to reach the current node) and the h_score (the predicted cost of the path ahead). This algorithm uses a simple sum of the g_score and the h_score to evaluate each node.
As previously stated in IDA* we do not save the visited nodes. Not saving the visited nodes has pros and cons. By not saving the visited nodes we have a chance of visiting the same node twice giving us a worse time complexity for the overall algorithm. However, by not saving our visited nodes we do not need as much memory. For our use case saving memory is important since we are dealing with a possible game tree of 43,252,003,274,489,856,000 nodes.
Alright, now that we have a better understanding of the algorithm we’re going to use let’s build it. The first thing will need to do is build our heuristics.
For our heuristics, we will take a simple brute-force approach and use the breadth-first search algorithm to check the nodes. Here we’re going to store the different states of the cube and the number of moves it took to get there from the solved cube in a hash table. By storing the cube states in a hash table, we have created a simple lookup table to know which state has the least amount of moves to be solved.
Now that we have our heuristics, we can implement the IDA* algorithm to solve the cube. Building the algorithm will use a simple DFS (depth-first search) algorithm with the scoring method described above (g_score + h_score). When visiting each node will pass in our previous node’s g_score to know the current cost. To determine the h_score will do a fast lookup of the node in our heuristics map. For the sake of simplicity if we find a node that is not in our heuristic map will set the h_score to 20 (god’s number). Here we could create some extra equations to get a better estimate but for our simple use case, this is not needed (if you have an equation for this feel free to leave it in the comments). With all that together we should get something like the code below.
Thanks
And there you have it, we have successfully created our Rubik’s cube solver. You can check a full version of the code on my GitHub here.
Thanks for reading. If you liked this, consider subscribing to my account to be notified of my most recent posts.
Reference
- https://en.wikipedia.org/wiki/Rubik%27s_Cube
- https://ruwix.com/the-rubiks-cube/how-to-solve-the-rubiks-cube-beginners-method/
- https://medium.com/@chaitanyaanimesh/calculating-the-number-of-permutations-of-the-rubiks-cube-121066f5f054
- https://en.wikipedia.org/wiki/Ern%C5%91_Rubik
- https://en.wikipedia.org/wiki/Big_O_notation
- http://kociemba.org/math/papers/rubik20.pdf
- https://en.wikipedia.org/wiki/Game_tree
- https://en.wikipedia.org/wiki/Iterative_deepening_A*
- https://en.wikipedia.org/wiki/A*_search_algorithm
- https://en.wikipedia.org/wiki/Heuristic_(computer_science)
- https://medium.com/towards-data-science/building-a-chess-engine-part2-db4784e843d5
