Rubik's cube algorithm reduced to 23 moves

The maximum number of moves required to collect a Rubik's Cube has been reduced to twenty-three. This mathematical problem was solved by a Stanford graduate Tomasz Rokitski. The strategy he developed was launched at the computer station, which confirmed the correctness of the calculations.

Rokitski applied the original approach. Instead of analyzing the individual moves, he took into account the shape of the cube and broke it into a set of its states. Total got 2 billion states (sets) with 20 billion elements in each. In this concept, moves are considered as pairs of “bound states” (cosets). Rokitski proved that a large number of states actually repeat each other and therefore can be ignored. But even after optimization, the computation of the entire model requires very large computational resources. The previous record (25 moves) took 1500 hours on a machine with a processor and Q6600 (1.6 GHz) and 8 GB of RAM. Now Rokitski borrowed 7.8 core-years of computing on a more powerful cluster in the famous Sony Pictures Imageworks film studio (calculations were performed while idle on the same machines where the special effects of Spider-Man 3 and the cartoon "Catch the Wave" were calculated): analyzed more than 200 thousand related states.

The theoretical work of Rokitski suggests that the optimal solution can be in 22 moves or even in 21 moves, but to verify this additional computational resources are required. So, to prove a solution in 22 moves, it takes about five to seven times more machine time: you need to calculate from 1 million to 1.5 million associated states.

The proof of the solution in 21 moves still looks fantastic, but it is fully consistent with the calculations of theoretical mathematicians who have devoted their careers to solving this problem. They assume that the minimum number of moves is somewhere in the beginning of the third ten.