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

TwistyPuzzles.com Forum

It is currently Thu Apr 17, 2014 8:05 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: Proof: 17x17x17 can take at least 379 moves
PostPosted: Sun Jul 03, 2011 6:41 am 
Offline
User avatar

Joined: Mon Nov 30, 2009 1:03 pm
Hi Twisty Puzzles fans,

Many people had already suspected that it could take many moves to solve my Over The Top 17x17x17 puzzle. But now we have proof.

Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow wrote this article, in which they calculate lower and upper bounds for the "God's number" for higher order nxnxn Rubik's Cube. Recently, it became know that the "God's number" for the 3x3x3 is 20. Even though exact numbers are yet unknown for higher orders, we now know some bounds.

The last equation seen on page 22 of the paper is this one.
    [(floor(n/2) - 1)^2 * log(24!/(4!)^6)]/log(6n) <= k
When you fill in n=17, then you find k=379.

This means that there exist at least one configuration, from which it takes at least 379 moves to solve the puzzle. Or to put it differently, it requires at least 379 moves to fully scramble the puzzle.

Oskar

_________________
Oskar's home page, YouTube, Shapeways Shop, Puzzlemaster, and fan club
Image.


Top
 Profile  
 
 Post subject: Re: Proof: 17x17x17 can take at least 379 moves
PostPosted: Sun Jul 03, 2011 9:40 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Oskar wrote:
It requires at least 379 moves to fully scramble the puzzle.
... or just one move with a really big sledgehammer. :lol:

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Proof: 17x17x17 can take at least 379 moves
PostPosted: Sun Jul 03, 2011 12:37 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
The paper was also mentioned in this thread.

Note that this formula is a very conservative lower bound -- it doesn't even count edge cubies, if I understand correctly. So the actual God's Number for the 17x17x17 is probably much higher.

The only purpose of the formula was to establish that it takes at least (some constant times) n^2 / log n moves to solve an nxnxn cube. For purposes of showing this asymptotic lower bound, it doesn't matter what the constant is, but for determining God's Number, it matters very much what it is.


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 1 guest


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