Scientists develop algorithm to solve Rubik's cubes of any size

Source: http://www.engadget.com/2011/07/01/scientists-develop-algorithm-to-solve-rubiks-cubes-of-any-size/

A computer solving a Rubik's cube? P'shaw. Doing it in 10.69 seconds? Been there, record set. But to crack one of any size? Color us impressed. Erik Demaine of MIT claims to have done just that -- he and his team developed an algorithm that applies to cubes no matter how ambitious their dimensions. Pretty early on, he realized he needed to take a different angle than he would with a standard 3 x 3 x 3 puzzle, which other scientists have tackled by borrowing computers from Google to consider all 43 quintillion possible moves -- a strategy known simply as "brute force." As you can imagine, that's not exactly a viable solution when you're wrestling with an 11 x 11 x 11 cube. So Demaine and his fellow researchers settled on an approach that's actually a riff on one commonly used by Rubik's enthusiasts, who might attempt to move a square into its desired position while leaving the rest of the cube as unchanged as possible. That's a tedious way to go, of course, so instead the team grouped several cubies that all needed to go in the same direction, a tactic that reduced the number of moves by a factor of log n, with n representing the length of any of the cube's sides. Since moving individual cubies into an ideal spot requires a number of moves equal to n², the final algorithm is n²/log n. If we just lost you non-math majors with that formula, rest assured that the scientists expect folks won't be able to apply it directly, per se, though they do say it could help cube-solvers sharpen their strategy. Other that, all you overachievers out there, you're still on your own with that 20 x 20 x 20.

Scientists develop algorithm to s! olve Rub ik's cubes of any size originally appeared on Engadget on Fri, 01 Jul 2011 12:57:00 EDT. Please see our terms for use of feeds.

Permalink   |  New Scientist  | Email this | Comments