Skip to main content

Finding Optimal Solutions to the Rubik’s Cube – 2. Mathematics

jhammer Rubik's Cube

Table of Contents

  1. Introduction
  2. Mathematics
  3. Representation
  4. Representation Evaluation
  5. Breadth-first Search
  6. Iterative Deepening Depth-first Search
  7. IDA*

2. Mathematics

Before we start trying to find optimal solutions to the Rubik’s cube, it would be a good idea to understand how large the search space is. In order to do that, it is helpful to split the analysis into separate pieces. We will separately consider:

  • Permutations of the corner pieces
  • Orientations of the corner pieces
  • Permutations of the edge pieces
  • Orientations of the edge pieces

If we can calculate each of these quantities, we should be able to multiply them together to count the total number of possible combinations.

Corner Permutations

There are 8 different corner pieces, each of which must be placed in a separate corner location. Imagine filling in the cube 1 corner piece at a time. Initially, none of the corners are placed. For the first corner, there are 8 possible locations, since none of them have yet been filled. For the second corner, there will only be 7 possible locations, since one of the locations was filled when we placed the first piece. Similarly, there will only be 6 possible locations for the 3rd piece, and so on. So for 8 corner pieces, we can count the total number of permutations as:

\(8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 8!\)

Therefore, there are 8! = 40,320 possible permutations of the corner pieces.

Corner Orientations

Each of the 8 corner pieces can be oriented in one of 3 ways because each corner has three colors. So logically, we should have:

\(3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 = 3^8\)

different orientations, right? Actually, not quite. It turns out that since the cube is a mechanical structure, once 7 of the 8 corners have been placed, there aren’t any more degrees of freedom for the last piece. The orientation of the last piece is determined completely by the orientations of the other 7. As a result, we only have:

\(3 * 3 * 3 * 3 * 3 * 3 * 3 * 1 = 3^7\)

possible orientations instead of the full \(3^8\).

Edge Permutations

We can calculate the number of edge permutations very similarly to how we calculated the number of corner permutations. There are 12 possibilities for the first edge, 11 for the second edge, and so on. So we should have:

\(12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 12!\)

possible edge permutations. However, we once again have to deal with the physical constraints of the cube. Mechanically, rotating in 90° increments for each of the 6 faces means that when the corners have an even permutation, so must the edges, and vice-versa. That effectively eliminates another degree of freedom, leaving us with:

\(\frac{12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1}{2} = \frac{12!}{2}\)

edge permutations in reality.

Edge Orientations

We can calculate the number of edge orientations very similarly to how we calculated the number of corner orientations. Each edge has one of two possible states (flipped or not flipped), and there are 12 edges. This gives us:

\(2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 2^{12}\)

orientations. As before, the orientations of the first 11 pieces uniquely determine the orientation of the last piece, eliminating a degree of freedom, which leaves us with:

\(2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 1 = 2^{11}\)

edge orientations that actually exist.

Putting It All Together

To summarize, we have:

  • \(8! = 40,320\) corner permutations
  • \(3^7 = 2,187\) corner orientations
  • \(\frac{12!}{2} = 239,500,800\) edge permutations
  • \(2^{11} = 2,048\) edge orientations

If we multiply those together, we get:

\(40,320 * 2,187 * 239,500,800 * 2,048 = 43,252,003,274,489,856,000\)

or 43 quintillion possible combinations. To put that number in perspective, a normal desktop computer evaluating 1,000,000 states per second would take approximately 1.2 million years to exhaust the search space. Clearly we will need to improve on that.