Curiosities: Permutation Puzzles from Archimedes to the Rubik’s Cube

The Rubik’s Cube is one of the most popular toys in history. It is also an example of a permutation puzzle, which have existed in mathematics in one form or another for at least 140 years. In hindsight, it is strange that the cube ever became so popular considering how hard it is. Very few ever solved it, and far fewer without a book or website as guide. (To his credit, the Hungarian professor of architecture who invented the cube took a few weeks but solved it.)

It might be surprising that more than thirty years after the 1982 craze, people are still discovering new things about the Rubik’s Cube. For example, mathematician Morley Davidson (Member 1995–96) and Tomas Rokicki recently showed that God’s number of the Rubik’s Cube is twenty-six. Their proof depends on a supercomputer calculation.

There is an almost inconceivably large number of positions for the cube––roughly 43 billion billion (4.3 x 1019). Although this number is enormous, it is finite, so there has to be in some sense “a worst-case scenario,” a position that is maximally mixed up.

The God’s number of the Rubik’s Cube is how many moves God, or a supercomputer, would take to solve it from this maximally mixed-up position.

What has been known for several years is that there are a few positions that require twenty-six moves to solve. The only known example is the “superflip composed with fourspot,” together with its rotations. The remarkable result of Davidson and Rokicki is that twenty-six moves suffice to solve every position.

For the last several years, we have had optimal solvers that can solve any given Rubik’s Cube position in the minimum number of moves, say in less than a second, on your desktop computer. So it might seem like this should resolve the question, with just brute force. Use these solvers to compute the minimal number of moves for every possible position, and then take the maximum over all of them, and you know the worst-case scenario. The problem is that there are 43 billion billion positions. So even if you could compute optimal solutions for, say, a million positions in one second, it would still take over a million years before you had calculated it for all of them.

Davidson and Rokicki discovered a number of clever reductions, greatly reducing the number of positions to check to only a few billion positions. Then roughly thirty-two CPU-years of donated time at the Ohio Supercomputer Center finished the computation in a matter of days.

Permutation puzzles are older than the Rubik’s Cube, and perhaps ancient. For one notable example, the familiar “15- puzzle,” where one slides square pieces around in a grid, went through a craze in the United States in 1880, almost exactly a hundred years before the Rubik’s Cube craze.

Sam Loyd, who has been called “puzzledom’s greatest celebrity . . . popularizer, genius” as well as a “huckster . . . and fast-talking snake oil salesman,” later further popularized the 15-puzzle by offering a prize of $1,000 to anyone who could find a sequence of moves that switch the 14 and 15. He must have been confident that it was impossible. He may have even known that this was a theorem already proved by mathematicians Wm. Woolsey Johnson and William E. Story in 1879.

The most ancient puzzle we know of that depends on permuting geometric pieces is probably the Stomachion. The Stomachion is a dissection of the square into fourteen convex pieces. Once taken apart, reassembling them into a square shape can be quite challenging.

The Stomachion caught the attention of the greatest mathematician of the ancient world, Archimedes, who wrote a treatise on the puzzle. This treatise was lost, but then recently part of it was recovered in a palimpsest. Archimedes asks for the number of distinct ways to reassemble the fourteen pieces into a distinct shape. If Archimedes gave us the answer, this was lost. However, mathematician Bill Cutler was able to compute the number of possible solutions to be 17,152, with the help of a computer. If Archimedes was able to do this calculation, how he did it remains a mystery.