James Tauber

journeyman of some

blog > 2008 > 03 > 27 >

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.

Categories:
prev « algorithms » next
prev « mathematics » next

Comments (3)

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.

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

Add a Comment

Created: March 27, 2008
Last Modified: March 28, 2008
Author: jtauber