Some people work out how to solve Rubik's cubes, but it is more common for people to memorize methodologies the others have published online and in books. Generally the algorithms that are relatively easy to remember involve many steps. A more advanced cuber will be able to find solutions with fewer steps. In speed cubing competitions, participants who can find a method of solving the cube with less steps will have an significant advantage.
In this article we'll describe how a neural network can be used to help find an efficient way of solving a Rubik's Cube. (Here's a link to the source code which uses Keras.)
Suppose we have a neural net which takes as input a vector X which represents the current state of a cube.
The output will be a vector Y with Y[i] = (probability that the cube can be solved in i steps) assuming a zero based indexing.
So if: \[\underline{Y}=(0,0,1,0,0, ..., 0)\] then we are 100% certain that the cube can be solved in 2 steps.
And if: \[\underline{Y}=(1,0,0, ..., 0)\] then it is a cube that can be solved in 0 steps, i.e. it is already solved.
We can create training data by starting with a solved cube and then randomly rotating the faces say n times. We then write a row in the training data file with the number n and the representation of the cube.
If you're interested in how this could be implemented in Java, then have a look at this code. On a regular laptop, it takes the code a few seconds to generate a training set with one million instances (rows).
The neural net that we built used a number of dense layers and then the last layer was softmax. It was implemented using Keras. The source code that we wrote can be found here.
How can the neural net be used to solve the cube?
Suppose the NN indicates that it can solve the cube in 8 steps. Then we can try 12 different rotations (each side of the six sides can be rotated either clockwise or anticlockwise). The neural net should then indicate that one of those options results in a cube that can be solved in 8-1=7 steps. And the other 11 can be solved in 8+1=9 steps. We choose the option that reduces the number of steps and then repeat until we have a solved cube.
In our first implementation the NN was very good at identifying if there were less than 6 steps to solve it. However if the solution involved more than 6 steps then it struggled.
One of the improvements we could make now is to use the NN to improve the quality of the training data.
When the training data is being generated, suppose one face is rotated consecutively 3 times clockwise. That could have been achieved with a single rotation anticlockwise. So the neural net may be able to find a faster way to solve the cube than is indicated in the data.
So we could apply the neural net to the input data and when shorter solutions are found, the data could be updated. The model can then be retrained with the improved data, which may enable the data to be improved even more.
