QED

Vorige maand bewees Tomas Rokicki dat de Rubik-kubus vanuit elke toestand kan opgelost worden in maximum 25 stappen. Hij schreef toen in zijn artikel Twenty-Five Moves Suffice for Rubik’s Cube:

Once this is done, we believe that with only a few more CPU months, we can show a new bound of 24 on the diameter of the cube group.

Nu is het zover, en zelfs beter dan verwacht: Rokicki heeft het aantal stappen ineens gereduceerd tot 23. Hij kondigde gisteren op zijn blog aan:

After solving more than 200,000 cosets, we have been able to show that every position of Rubik’s cube can be solved in 23 or fewer face turns.

Dezelfde technieken werden gebruikt als in het bewijs van vorige maand, enkel met meer computerkracht. En Rokicki kijkt weeral verder:

To prove 22 would require, using this technique, solving somewhere between 1 and 1.5 million cosets. We are investigating refinements to our techniques to reduce the CPU time required.

Wiskundigen vermoeden dat het maximaal aantal stappen rond de 20 ligt, dus het zou wel eens kunnen dat Rokicki binnenkort het kleinste aantal stappen vindt dat nodig is om een willekeurige toestand van de Rubik-kubus op te lossen, het aantal stappen dus van God’s algorithm.