Google Helps Find Simplest Solution to Rubik’s Cube
No matter how mixed-up it is, the Rubik’s Cube can be solved in 20 moves or fewer, say a team of researchers who used computer time donated by Google to run complex algorithms to prove it.
That means all the 43,252,003,274,489,856,000 positions of the Cube require no more than 20 steps to get the Cube in shape.
“It took 15 years after the introduction of the Cube to find the first position that provably requires 20 moves to solve,” says the team on their webpage. “It is appropriate that 15 years after that, we prove that 20 moves suffice for all positions.”
The Rubik’s Cube, a 3-D puzzle, was invented in 1974 by a Hungarian sculptor and professor Erno Rubik. Rubik licensed it to be sold as a toy and since then it has turned into the world’s top-selling puzzle. As of January 2009, at least 350 million cubes have sold worldwide.
Solving the Rubik’s Cube can take anywhere from seconds to hours. The official championship record for 2008 is 7.08 seconds.
The shortest sequence of moves that the most efficient algorithm takes to solve the Cube is known as “God’s number.” In 1981, it was thought a maximum of 52 moves was required. By August 2008, it had been reduced to 22.
To get their number, the group — comprising math teachers, a Google engineer and a programmer — broke the larger problem of solving the Rubik’s Cube into 2,217,093,120 smaller problems. Each of these smaller problems had 19,508,428,800 different positions.
The subproblems were small enough to fit in the memory of a modern PC. But it would take an Intel four-core, 2.8-GHz Nehalem chip-based desktop computer 1.1 billion seconds, or about 35 years, to perform the calculation. So the team turned to the impressive computing power that Google has to solve the problem. (Google won’t disclose exactly what kind of computing resources it offered to the group.)
If you’d like to geek out further on the math of solving the Rubik’s Cube efficiently, the Cube 20 site has all the details.
See Also:
Lego, Motorola Droid Combine to Solve the Rubik’s Cube
iPhone App Solves Rubik’s Cube in 20 Moves or Better
Universal ‘Rubik’s Cube’ Could Become Pentagon Shapeshifter …
Jan. 30, 1975: Rubik Applies for Patent on Magic Cube
The 30-Year Rubik’s Invasion Continues
Photo: (Marc Brakels/Flickr)
Fuente: Gadget Lab
