on the robust difficulty of rubik’s cubes
I’ve been amused (not in an evil genius way) by the once-and-future popularity of the Rubik’s cube. Had one as a kid, memorized its method, got a couple of sub–2-minute times, put it down.
Fast forward 35 years; now my son is mildly amused by the Rubik’s cube (amused enough to let his old man persuade him to make a Rubik’s Cube Halloween costume, anyway), and I decide to learn a new method (currently Roux, but who knows if it’ll last).
Along the way, though, I start wondering: how do they make sure that “scrambled” cubes at speedsolving competitions are about equally hard to solve? What if Joe Plotnik just happens to get one that’s easy?
It turns out… that’s very unlikely, due to a kind of a cool property that Rubik’s cubes have. Specifically, given a random (reachable) position of the cube, there’s about a 94% likelihood that it requires either 18 or 19 moves to solve.
These numbers come from Cube20, a team that used lots of compute power back in 2010 to determine the distribution of “moves required.” One thing they didn’t do (erm, on their front page, anyway) was to show the CDF of these numbers. Here it is:
The cool thing about this is the incredibly narrow band of likelihood; if you simply generate a position at random from the set of all possible positions, there’s a rounds-to-zero-percent chance of it requiring 15 moves or less, 3% of getting 16 moves or less, and a rounds-to–100% chance of it requiring 19 moves or less. There’s more than a 93% chance that it will require either 18 or 19 moves.
So… cubing competitions are almost certainly fair. Neat!