Optimal 2x2 Cube Solver

Solving a Rubik's Cube is easy. But solving it in fewest moves possible every time isn't a thing that humans can handle. In fact, computers are also not enough for this problem today. However, as 2x2 cubes are less complex than the 3x3 ones, it would worth trying to write a program for the Pocket Cube.

To reinforce this idea, let's look at some facts about 2x2x2 Rubik's Cube:

• There are 3, 674, 160 possible combinations. This number is not that much, especially compared to the 3x3 Cube, which has over 43 quintillion possible combinations.
• Any cube configuration can be solved in up to 11 turns. This will make more sense while explaining the algorithm.

Algorithm Strategy

The first approach is to try every possible turn until the cube is solved. Well, we'd apply all possible notations to scrambled cube. If none of them worked, we'd again apply all notations to previously generated positions, and repeat this process, unless we reach a solved position.

That sounds reasonable. now let's calculate how many turns we need.

There are 18 possible turns that you can apply to Rubik's Cube, to the Pocket Cube as well. So if the cube is solvable in one move, we need to check for at most 18 moves. If scramble requires at least 2 moves, after making 18 moves in step 1, we'll apply at most 18×18 additional moves in step 2. For n required moves, we must try 18ⁿ turns in nᵗʰ step. We also know to limit for n, even in worst scenario, we won't have more than 11 steps.

Unfortunately, as numbers grow exponentially, we have a huge number like 6.4×10¹³ in last step. Despite future improvements to the algorithm, it doesn't seem to be calculable.

Fortunately, there is another fact that can help us. For 2x2 Cube, half of these 18 notations does the same thing with the other half. For example, F and B' conclude with the same positions. So we can dismiss the half and continue with 9 notations.

Also, we won't make any repeating moves. For example, if current notation series ends with U, it can't continue with one of U, U' or U2. Therefore, we're going to check for 6 moves for each step, except the first one.

By these updates we get this series from the rule 9×6ⁿ⁻¹:

9 - 54 - 324 - 1944 - 11,664 - 69,984 - 419,904 - 2,519,424 - 15,116,544 - 90,699,264 - 544,195,584

This is much more better, isn't it? But it's still not enough, especially the number on the step 11 scares me. Luckily 11 moves requiring scrambles are too rare, as you can see below:

Future Improvements

Now the algorithm will work, but several improvements can be made for quicker solutions. For example, some of the notation series do the same thing. We can track only one series and abandon the other one.

There are various attemptable code implementations. I saved series and positions in Python lists, it's kind of brute force. There are absolutely more effective ways which I'm too lazy to try, such as recursion. Also selecting a faster language makes sense.

Showcase

Here's the quick view of my program, which is frankly speaking horrible. I didn't come across any solution exceeding one minute, but it is certainly perfectible: