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

TwistyPuzzles.com Forum
 It is currently Fri Apr 18, 2014 8:27 am

 All times are UTC - 5 hours

 Page 1 of 1 [ 3 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: The Search for God's Number on Higher Order CubesPosted: Fri Jul 01, 2011 8:31 pm

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

 Post subject: Re: The Search for God's Number on Higher Order CubesPosted: Fri Jul 01, 2011 10:45 pm

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

http://arxiv.org/abs/1106.5736

Top

 Post subject: Re: The Search for God's Number on Higher Order CubesPosted: Sat Jul 02, 2011 1:25 am

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 3 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 2 guests

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

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic