God exists and he plays with Rubix cubes.

[Jason Tandro]

Courtesy: http://videogames.yahoo.com/events/plugged-in/study-uncovers-every-possible-rubik-s-cube-solution/1407748




WASHINGTON (AFP) – An international team of researchers using computer time lent to them by Google has found every way the popular Rubik's Cube puzzle can be solved, and showed it can always be solved in 20 moves or less.

The study is just the latest attempt by Rubik's enthusiasts to figure out the secrets of the cube, which has proven to be altogether far more complicated that its jaunty colors might suggest.

At the crux of the quest has been a bid to determine the lowest number of moves required to get the cube from any given muddled configuration to the color-aligned solution.

"Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube," said the team of mathematicians, who include Morley Davidson of Ohio's Kent State University, Google engineer John Dethridge, German math teacher Herbert Kociemba and Tomas Rokicki, a California programmer.

"There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized by a mortal typically require more than forty moves."

One may suppose God would use a much more efficient algorithm, one that always uses the shortest sequence of moves; this is known as God's Algorithm. The number of moves this algorithm would take in the worst case is called God's Number. At long last, God's Number has been shown to be 20."

The research, published online, ends a 30-year search for the most efficient way to correctly align the 26 colored cubes that make up Erno Rubrik's 1974 invention.

"It took fifteen years after the introduction of the Cube to find the first position that provably requires 20 moves to solve," the team said. "It is appropriate that fifteen years after that, we prove that twenty moves suffice for all position."

Using computers lent to them by Google -- the company won't disclose how many or how powerful they are -- the team crunched through billions of Cube positions, solving each one over a period of "just a few weeks."

The study builds on the work of a veritable pantheon of Rubik's researchers, starting with Morwen Thistlethwaite who in 1981 showed 52 moves were sufficient to reach the solution from any given Cube position.

By May 1992, Michael Reid showed 39 moves was always sufficient, only to be undercut a mere day later by Dik Winter, who showed 37 moves would work.

Rubik's enthusiasm extends not only to God's number, but the speed with which the tricky puzzle can be solved.

The current world record holder is Dutch Erik Akkersdijk who successfully solved the puzzle in just 7.08 seconds.

[EverPhoenix]

ive heard people even grease up their cubes so they smoothly rotate. watching a pro solve one is pretty amusing.

[chicken]

science is fucking everywhere...

and WHAT THE HELL: 30 years of studying? O_o

[tay120n64]

I read this yesterday. It's amazing what people get paid to do.

[Yet One More Idiot]

Wow, they've actually solved it? I thought there were so many possible positions/orientations of the cubies, that it would take many more years before it would be completely solved for every starting position!

My favourite fun fact about the Rubik's Cube is that famously, ever since it first became available, it's always been marketed as having "BILLIONS of combinations", because the promoters felt that using the more accurate statement "QUADRILLIONS of combinations" (10^24, btw), might sound to the mathematically uninclined to be a made-up word.

[EverPhoenix]

i could theoretically (given effort and a shit-ton of memory) write a comp program that could solve said cube in the 20 moves or so. it might take a little while to solve though.

for those inclined, A* search with a crappy 'dots out of place' heuristic.

[psychokind]

so if I find a rubic cube on the street, and realize I only need one move to complete it, I'm better than god?

[EverPhoenix]

psychokind wrote:

so if I find a rubic cube on the street, and realize I only need one move to complete it, I'm better than god?

no, you are better than god if you can solve that particular puzzle in EXACTLY 20 moves. solving it in one move is boring, be interesting. oh and no repeated states allowed

[psychokind]

EverPhoenix wrote:

psychokind wrote: so if I find a rubic cube on the street, and realize I only need one move to complete it, I'm better than god? no, you are better than god if you can solve that particular puzzle in EXACTLY 20 moves. solving it in one move is boring, be interesting. oh and no repeated states allowed

I just wanted to show the blasphemy in this statement

[EverPhoenix]

psychokind wrote:

EverPhoenix wrote: psychokind wrote: so if I find a rubic cube on the street, and realize I only need one move to complete it, I'm better than god? no, you are better than god if you can solve that particular puzzle in EXACTLY 20 moves. solving it in one move is boring, be interesting. oh and no repeated states allowed I just wanted to show the blasphemy in this statement

thats ok, im not religious anyway.