Rubik's cube - the order of God's Number
Rubik's cube - the order of God's Number
Written by Mike James   
Wednesday, 29 June 2011

God's number is the smallest number of moves it takes to solve a general Rubik's cube. We still don't know the size of God's number for any cube other than the standard 3x3x3 but we do now know how it varies with the size of the cube and the remarkable thing is that it gets easier as the cube gets bigger.

 

Given we are in the business of creating algorithms you can't help but wonder how many moves are required in general to solve a Rubik's cube. To be precise we would like to know what has come to be called "God's number", i.e. the smallest number of moves needed to solve the worst possible cube. In the case of the familiar 3x3x3 cube it was proved that 20 moves are always enough to solve even the hardest mixup. Finding this result took 35 years of computer time.

The next task is to find God's Number for generalized cubes - usually larger and so not as easy to solve using brute force enumeration. The question is how does the difficulty of the problem scale with the size of the cube?

cube

There is now an answer to this question in a paper to be presented at the 19th Annual European Symposium on Algorithms in September, written by researchers from MIT, the University of Waterloo and Tufts University.

A dumb approach to solving the problem is to perform a set of moves that places a single sub-cube in its correct position and repeat until all the faces are complete. This gives an upper bound of order n^2 - as the number of sub-cubes  all of the faces is proportional to n^2, However, it is well known that you can usually do better by using moves that place multiple sub-cubes into their correct location. These heuristics have now been made formal and this resulted in order n^2/logn being the new upper bound. Now this has also been shown to be the lower bound in the same paper.

What this means is that the smallest number of moves required to solve the nxnxn Rubik's cube is proportional to n^2/log(n).

Why is this surprising?

Well the number of moves being proportional to n^2 is just a reflection of the fact that more surface faces mean more moves, but why is this reduced by log(n) as the size of the cube goes up? There have to be increasing numbers of shortcuts to the simple solution as the cube gets bigger.

rubikgraph

How n^2/log n varies with n and how much smaller it is than n^2

 

Notice that this result doesn't tell us God's Number for a cube of any size, only that it is proportional to n^2/logn.

In addition the paper derives an asymptotically optimal solution for solving the general cube in the worst case. It also raises the question of whether finding an optimal solution to the general cube is NP hard or not.

Algorithms for Solving Rubik's Cubes (pdf)

See also:

Rubik's cube breakthrough

 

cube

Banner


Google Introduces Mobile Sites Certification
10/04/2017

Google has added a new certification with a free exam and a set of free resources for exam preparation. It covers best practices for creating, managing, measuring and optimising mobile websites.& [ ... ]



This Just In: Fake News Packs a Lot in Title, Uses Simpler, Repetitive Content in Text Body, More Similar to Satire than Real News
30/03/2017

Fake news, well you know it when you see it because it's news with its facts all wrong. Now researchers have concluded that this isn't the case. In fact fake news is more like satire than news in styl [ ... ]


More News

<ASIN:B002379VTE@COM>

<ASIN:B00000JD5S@COM>

<ASIN:B0006G3B68@UK>

<ASIN:B0009QVM0W@UK>

<ASIN:1593272162>

<ASIN:0553140175>

<ASIN:1402753136>

<ASIN:157912805X>

Last Updated ( Wednesday, 29 June 2011 )
 
 

   
Banner
Banner
RSS feed of news items only
I Programmer News
Copyright © 2017 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.