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

TwistyPuzzles.com Forum
 It is currently Thu Mar 13, 2014 9:18 pm

 All times are UTC - 5 hours

 Page 1 of 1 [ 3 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Proof: 17x17x17 can take at least 379 movesPosted: Sun Jul 03, 2011 6:41 am

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

_________________
.

Top

 Post subject: Re: Proof: 17x17x17 can take at least 379 movesPosted: Sun Jul 03, 2011 9:40 am

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.

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

Top

 Post subject: Re: Proof: 17x17x17 can take at least 379 movesPosted: Sun Jul 03, 2011 12:37 pm

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

 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