SIAM News Blog

Solving the Rubik’s Cube with Group Theory

The editors of SIAM Review recap the SIGEST paper in the September 2014 issue of SIREV:

The SIGEST paper in this issue, “The Diameter of the Rubik’s Cube Group Is Twenty,” by Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge, is from the SIAM Journal on Discrete Mathematics.

The year 2014 marked the 40th birthday of the Rubik’s cube puzzle. I expect that most readers know what Rubik’s cube is, and direct the few of you who do not to this New York Times piece, where you’ll get a far better account of the story than any printed page will ever give you.

The main result in the paper is that Rubik’s cube can be solved from any initial position in 20 moves or fewer. The proof is via an exhaustive computation from all 4.3×1019 starting positions. The computation is made tractable with an astute application of advanced group theory to reduce the size of the search space and enabled by a donation of 109 seconds of CPU time from Google.

Read the paper! (Requires subscription or SIAM membership):

The Diameter of the Rubik’s Cube Group Is Twenty

SIAM Review, 56(4), 645-670.

blog comments powered by Disqus