Twenty-Five Moves Suffice
I've talked about the Rubik's Cube before and linked to last year's paper by Kunkle and Cooperman proving Twenty-Six Moves Suffice for Rubik’s Cube.
Now Tomas Rokicki has proved that Twenty-Five Moves Suffice for Rubik's Cube. Actually, what he proved is that no configuration takes 26. If x <= 26 and x != 26 then x <= 25 QED.
It is known that some configurations need 20 moves and that no configuration needs 21. So the possible optimal move maxima are 20, 22, 23, 24 and 25.
Via Dave Long, I also found out about Joyner's Mathematics of the Rubik's Cube (pdf) which became the book Adventures in Group Theory.
UPDATE: Actually, I don't think it's been proven that no configuration needs 21, just no configuration has been found that needs 21.
UPDATE 2: David Joyner informs me a 2nd edition of his book is coming out soon.
Comments (3)
James Tauber on March 27, 2008:
Joe, they explicitly define a "move" as a 90 or 180 degree rotation of a face in either direction.
Some call a 180 degree rotation 2 moves. Others allow the middle section to be rotated as a single move.
But the paper in question and its predecessor use the face rotation definition.
Mike Hansen on March 28, 2008:
David Joyner has also included some code in Sage ( a free, open-source computer algebra system using Python ) which allows for some computation with the Rubik's cube. You can find some autogenerated documentation here: http://www.sagemath.org/doc/html/ref/module-sage.groups.perm-gps.cubegroup.html
Last Modified: March 28, 2008
Author: James Tauber
Joe Weaks on March 27, 2008:
I find this interesting. I do wonder if the notion of what constitutes a "move" is not an ontological concept. In my world, we argue about how many minor agreements there are in the synoptic gospels when mostly we're arguing about what constitutes a single agreement.