Back to the 80s

The Rubiks Cube seems like a pop-culture relic from the 80s; but since more than a decade, it has made a revival (and might become more popular than ever?). I too am a big fan of this "toy" and have spend more hours on solving this and related puzzles, than anyone can image. Being a computer scientist it seemed only natural to not only solve it myself, but to try and teach a computer to solve a cube as well. And here is my approach.
Scrumbled Rubik's Cube

The boring solution

A little excursion into the way humans solve the Rubiks Cube: we memorize a couple of “algorithms”, so sequences of turns, designed to switch only a few pieces of the cube around. Then we go from bottom to top, layer by layer and switch each piece, where it belongs. The algorithms needed to switch the pieces around get more complex, the close you get to the finish line. But after applying dozens of them (and executing probably more than a hundred turns) we will finally have solved the cube.

The reasons why we do it that way, is that we humans are dumb; there are too many constellations of the cube and we can not keep track of all pieces we are gonna move with each turn. Thats fact. But a computer does not have that limitation! That is the reason, why I didn’t want to teach the computer to solve the cube the exact same way, we humans do it. That would just be a lot of repetative work and when finished, the program would just show me the same solution I know anyways.

Some examples of Last-Layer algorithms.

The cool solution

Before I tell you, what my cool solution is, we need to clarify some others piece of theory. Firstly, it has been mathematically proven, the maximal number of necessary moves to solve ANY scrambled Rubiks Cube is 20. That means, a computer could produce a solution as short as only 20 turns. That would be awesome, wouldn’t it? Secondly, a Rubiks Cube has 6 sides and we can turn each of them into 3 different positions (excluding the full 360° turn). This means at any given point we can choose between 18 different moves to apply.

For the fraction of a second I thought: “Oh well, I can just let computer search all 20-move-long sequences for a solution. Thats only \(18^{20}\) possibilities.” Then I realized, that this might still be a little too many, after all \(18^{20}=12748236216396078174437376\). For reference, if my program could check one billion possibilities in a second (which is in itself questionable), my program would, in the worst case, still run almost as long as the age of our earth. Clearly this seems like a lost cause. But I still liked the idea of searching the possible solutions for the right one, so I implemented something similar.

In detail

My solver has built-in memory, persisting all cubes it ever solved and with what solution it got solved. Then, given a new cube, it will check, if there is a cube in 4-move distance that it already knows. That means, as we have 18 possible moves, the solver searches the tree up into a distance of 4, so up to \(18+18^2+18^3+18^4=111150\) cubes.

Trying find a close match with a known cube.

If there is a match, the solver combines the moves to get from the current cube to the known cube and the solution of the known cube. It has thereby solved a new cube and will of course rembember the solution to this cube.

Solving the cube when a match has been found.

Major drawbacks

As you might have already realized, that approach, however “simple” it is, has three major problems.

  • It the beginning, the solver doesn’t know any cubes. We therefore have to train it with easy and more and more difficult cubes. This corresponds to teaching it how to solve cubes with one turn, then two turns and so on.
  • When given a new cube, the solve looks for a close match. But of course there is no guarantee it will find one. If it does not find one, it will not solve the cube
  • We persist all solved cubes in memory. As we already realized, there are endlessly many of them, so the solver will never remember all cubes and therefore most likely not be able to solve any cube you throw at him.

So even after some training, the solver takes a while to find solutions and is not able to solve every cube, so I as a human are still faster and more consistent than the computer. However, despite of the drawbacks, if the solver finds a solution it is always way shorter (in number of moves) than any solution I can come up.

Here is a sample run of the solver, where we firstly train some scrambles and then try to solve a randomly generated cube.

Start training...
Training scrambles with length 1...
Skipping length 1, all scrambles already known.
Success on training length 1: 500/500
Training scrambles with length 2...
Skipping length 2, all scrambles already known.
Success on training length 2: 500/500
Training scrambles with length 3...
Success on training length 3: 500/500
Training scrambles with length 4...
Success on training length 4: 500/500
TRAINING REPORT:
Overall success: 2000/2000
Scrambles known:
Length 0: 1/1
Length 1: 18/18
Length 2: 324/324
Length 3: 3000/5832
Length 4: 3000/104976
Applying scramble: R2 F' B' D' F U D2 U'
             _____________
             | B | G | Y |
             _____________
             | B | B | B |
             _____________
             | B | B | B |
             _____________
_______________________________________
| R | Y | Y || O | O | O || W | W | R |
_______________________________________
| G | O | O || W | W | Y || R | R | G |
_______________________________________
| G | W | O || G | W | Y || R | R | G |
_______________________________________
             _____________
             | Y | G | B |
             _____________
             | R | G | B |
             _____________
             | W | O | W |
             _____________
             _____________
             | R | Y | O |
             _____________
             | R | Y | O |
             _____________
             | W | Y | G |
             _____________
Success! Solution: D2 F' D F B R2
             _____________
             | B | B | B |
             _____________
             | B | B | B |
             _____________
             | B | B | B |
             _____________
_______________________________________
| O | O | O || W | W | W || R | R | R |
_______________________________________
| O | O | O || W | W | W || R | R | R |
_______________________________________
| O | O | O || W | W | W || R | R | R |
_______________________________________
             _____________
             | G | G | G |
             _____________
             | G | G | G |
             _____________
             | G | G | G |
             _____________
             _____________
             | Y | Y | Y |
             _____________
             | Y | Y | Y |
             _____________
             | Y | Y | Y |
             _____________

If you are interested in how I implemented this in detail, want to find out how to use the solver and try yourself or suggest an improvement, you can check out the project on my GitHub.