Mathematicians from the Massachusetts Institute of Technology estimated the number of moves needed to solve the Rubik’s cube (that is, bringing the cube faces to the same color) of an arbitrary size. The preprint of their article (pdf) appeared on arXiv.org.
Rubik’s cube studies by mathematicians began in the early 80’s of the last century (the puzzle itself was created in 1974). As it turned out, the group of symmetries of the cube, acting on the set of its squares, is rather complicated and difficult to study. In 2010, game theory experts calculated on the supercomputer all 43 252 003 274 489 856 000 possible initial positions for the standard Rubik’s cube (3 by 3 by 3) and found that from any initial position the cube can be collected in just 20 moves.
In the framework of the new study, scientists were interested in the asymptotic estimate of the number of movements necessary to solve the Rubik’s cube (although, in this case, it would be more correct to call it a rectangular parallelepiped) with sides of arbitrary size. The parameter n is the length of the maximum side of the puzzle, and “asymptotic” in the name means that the estimate is not exact, but with an increase in n, the optimal number of moves increases as an estimate.
Researchers managed to establish that in the general case the number of moves is O (n2) – that is, the number of cube movements needed to solve the problem increases approximately as a square n multiplied by some constant. At the same time, scientists proposed a direct decision algorithm that implements the proposed assessment. In two particular cases, scientists have been able to improve this result.
So, it turned out that for the “cubic” Rubik’s cube, that is, the puzzle with the sizes n on n by n, and for the “rope” of Rubik – the puzzle with the sizes n on n by 1, the score looks like O (n2 / log n). The last effect is due to the fact that in one movement in similar puzzles one can put several squares in the right place at once.
The problem of solving the Rubik’s cube belongs to the class of algorithmic problems of reorganization. A typical example of such a problem, encountered in practice, is the permutation of the boxes in the right way in the warehouse.
