• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

Rubik can be solved in 20 moves - computers found

Joined
5/2/06
Messages
11,750
Points
273
<object classid='clsid:D27CDB6E-AE6D-11cf-96B8-444553540000' id='TelegraphPlayer-7940813' width='560' height='315' codebase='http://fpdownload.macromedia.com/get/flashplayer/current/swflash.cab'><param name='movie' value='http://www.telegraph.co.uk/telegraph/template/utils/ooyala/telegraph_player.swf'/><param name='salign' value='LT'/><param name='allowFullScreen' value='true'/><param name='allowScriptAccess' value='always'/><param name='scale' value='noscale'/><param name='wmode' value='window'/><param name='bgcolor' value='#000000'/><param name='FlashVars' value='embedCode=IzZDVuMTpwtB6QCRrXd3D2fQnSRw8VBq&autoplay=1&offSite=true&showTD=true'/><embed type='application/x-shockwave-flash' src='http://www.telegraph.co.uk/telegraph/template/utils/ooyala/telegraph_player.swf' pluginspage='http://www.adobe.com/go/getflashplayer' menu='false' quality='high' play='false' name='TelegraphPlayer-7940813' height='315' width='560' salign='LT' allowFullScreen='true' allowScriptAccess='always' scale='noscale' wmode='window' bgcolor='#000000' flashvars='embedCode=IzZDVuMTpwtB6QCRrXd3D2fQnSRw8VBq&autoplay=1&offSite=true&showTD=true'></embed></object>​

The “riddle” of the minimum number of moves required to solve any configuration of the popular toy has stumped its users, and mathematicians, for almost three decades.

But now the team of researchers, based in Palo Alto, California who used Google computers, have discovered that any combination can be solved in no more than 20 moves.

Experts say this figure is known as "God's number", which is based on an assumption that even an “all knowing entity” could not solve the puzzle faster.

The results suggest there are more than 100,000 starting positions that can be solved in exactly 20 moves although the majority of solutions take between 15 and 19 moves to piece together.

The researchers combined the search engine giant’s computing power with mathematical expertise to check more than 43 quintillion (43,252,003,274,489,856,000 to be exact) possible jumbled positions the cube can take.

Prof Morley Davidson, a mathematician from Kent State University, Ohio, a member of the team, told the BBC: "We now know for certain that the magic number is 20.

"It's come full circle for me. Rubik's cube was an icon of the 80s when I was growing up and was the reason I went into mathematics.
"It's the universal popularity of the puzzle – it's probably the most popular puzzle in human history."

The initial results have been published online and Prof Davidson said they would now be submitted to peer-reviewed journals.

Tomas Rokicki, a programmer who has spent the past 15 years searching for a solution, said the team’s computer algorithm could try out 1 billion cubes per second. Previous computer methods could only solve around 4,000 possible cubes a second.

“The primary breakthrough was figuring out a way to solve so many positions, all at once, at such a fast rate,” he told the New Scientist magazine.

To simplify the problem, the team of researchers used the mathematics technique called group theory.

According to the New Scientist, they first they divided the set of all possible starting configurations into 2.2 billion sets – each containing 19.5 billion configurations – according to how these configurations respond to a group of 10 possible moves.

This grouping then allowed the team to reduce the number of sets to just 56 million, by exploiting various symmetries of a cube.

The team's algorithm rapidly matched moves to the correct starting point, allowing them to solve each set of 19.5 billion in less than 20 seconds.

At this speed completing the entire task would take around 35 years for an ordinary home computer.

In 2007, The Daily Telegraph reported that any configuration of a Rubik's cube could be solved in 26 moves, or less.

Others have since found it to be less, although Prof Davidson said this was “pure religion”.

Invented in 1974 by Professor Erno Rubik, the Rubik's cube was an instant success when it was first exported from Hungary in 1980, becoming the world's fastest-selling toy.

The 64-year-old reclusive Hungarian professor has since seen his cube achieve 350 million sales in the three decades since.

Still obtaining a cult following, almost 40,000 entries on YouTube feature tutorials and video clips of quick solutions.

Last year the 360, a new game from the Rubik's cube inventor went on sale.
 
There has to be a more elegant way to prove this than to brute force your way through this many starting configurations, even with the groupings. What are they going to do for the 4x4 and the 5x5 cubes?
 
There has to be a more elegant way
The proof for _many_ things was quite inelegant. Take Fermat's Last theorem. It was long enough to be its own book.

Though I share your sentiment :P
 
There has to be a more elegant way to prove this than to brute force your way through this many starting configurations, even with the groupings. What are they going to do for the 4x4 and the 5x5 cubes?

I don't think there's a simple proof for the four-color theorem (yet) either -- it's a messy proof using close to 400 basic configurations. It leads to interesting speculation that the demonstration of some results may not be amenable to slick deductive reasoning but may involve a mix of brute force, heuristics, and deduction. And since computing power is being brought in for the brute force part, a human may not be able to verify the demonstration.

A propos Rubik's cube, I know of at least a couple of books -- one by David Singmaster -- which explain basic ideas of group theory using the cube as an example.
 
Back
Top