Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Wed Apr 16, 2014 6:00 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: The Search for God's Number on Higher Order Cubes
PostPosted: Fri Jul 01, 2011 8:31 pm 
Offline
User avatar

Joined: Fri Jan 07, 2011 2:37 pm
"Last August, 30 years after the Rubik’s cube first appeared, an international team of researchers proved that no matter how scrambled a cube got, it could be solved in no more than 20 moves. Although the researchers used some clever tricks to avoid evaluating all 43 quintillion of the cube’s possible starting positions, their proof still relied on the equivalent of 35 years’ worth of number crunching on a good modern computer.

Unfortunately, for cubes bigger than the standard Rubik’s cube — with, say, four or five squares to a row, rather than three — adequately canvassing starting positions may well be beyond the computational capacity of all the computers in the world. But in a paper to be presented at the 19th Annual European Symposium on Algorithms in September, researchers from MIT, the University of Waterloo and Tufts University establish the mathematical relationship between the number of squares in a cube and the maximum number of moves necessary to solve it. Their method of proof also provides an efficient algorithm for solving a cube that’s in its worst-case state."

I copied that from this MIT news article. It states later in the article that their solutions aren't always optimal.


Top
 Profile  
 
 Post subject: Re: The Search for God's Number on Higher Order Cubes
PostPosted: Fri Jul 01, 2011 10:45 pm 
Offline
User avatar

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
The paper is here:

http://arxiv.org/abs/1106.5736


Top
 Profile  
 
 Post subject: Re: The Search for God's Number on Higher Order Cubes
PostPosted: Sat Jul 02, 2011 1:25 am 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
Demaine was my Ph.D. co-supervisor at MIT. We worked on -- surprise -- games and puzzles. We talked about nxnxn Rubik's Cubes a few years ago, but I told him they were basically uninteresting, from an algorithms perspective -- the general algorithm is essentially trivial. (We were focusing on problems that were computationally intractable, NP-complete or worse.) Shows what I know. Erik is very good at finding interesting aspects of a problem when it looks like there are none.

What he and his co-authors showed here is that O(n^2 / log n) moves are necessary and sufficient to solve an nxnxn cube. It's not an attempt to find God's Number for higher-order cubes. I haven't read the paper yet, but it does seem as if there could be practical application for high-order cubes -- standard approaches would take O(n^2) moves.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group