Tuesday, August 10, 2010

A Rubik's Cube Can Always Be Solved In 20 Moves Or Less [Puzzles]

Source: http://gizmodo.com/5609032/a-rubicks-cube-can-always-be-solved-in-20-moves-or-less

A Rubik's Cube Can Always Be Solved In 20 Moves Or LessUsing 35 years of Google-donated CPU time, a team of researchers found that every possible configuration of the Rubik's Cube can be solved in 20 moves or less. Personally, I've almost got all the yellows on one side.

That's right: every one of the Rubik's Cube's 43,252,003,274,489,856,000 possible positions can be solved in 20 moves or less.

That figure—the maximum number of moves it takes to solve the Cube using the most efficient algorithms possible—is called God's Number. In 1981, it was thought to be as high as 52. By 2005 it was at 28. And now, using a program that can solve the Cube in 20 seconds over 35 CPU-years of idle computer time donated by Google, it's been proven to be exactly 20.

Of course, for the true Cube-heads, there's plenty of interesting math behind the discovery. For the rest of us, there's just the nagging knowledge that we've gone about 400 rotations too far. [Cube 20 via Slashdot]

Image credit M. Christian