8
$\begingroup$

Suppose you have a Rubik's cube, $10,000$ blocks across (so, $600,000,000$ total tiles), scrambled. Assuming an ideal solving algorithm, approximately how long will the cube take to be solved, given one quarter turn can be made every 2.8 seconds?

$\endgroup$
  • $\begingroup$ Do ou have some reason to think this is known? Or possible to compute with existing technology? $\endgroup$ – GEdgar Jan 17 '19 at 1:17
  • $\begingroup$ @GEdgar I know that the optimal algorithm for a rubiks cube of arbitrary size might not be known, but I think an approximation is possible. $\endgroup$ – qazwsx Jan 17 '19 at 1:18
  • 1
    $\begingroup$ The so-called "God's Number" —counting the number of moves required to solve the $3\times 3\times 3$ cube— is known to be $20$; the number of quarter turns (as opposed to moves) is reportedly $26$. So, make your best guess about how $26$ scales to a $10000\times 10000\times 10000$ cube, and multiply by $2.8$. $\endgroup$ – Blue Jan 17 '19 at 1:38
  • $\begingroup$ @Blue But how does the God's Number scale with cube size? Its not just a linear scale. God's number for 2 by 2 by 2s is 14. $\endgroup$ – qazwsx Jan 17 '19 at 1:52
4
$\begingroup$

According to https://arxiv.org/abs/1106.5736 the asymptotic bound for God's Number on higher order cubes is:

$$\Theta(n^2/\log n)$$

But this is only asymptotic, so you can't just plug in $n$ and expect to get the exact right answer. But we use it as a very loose approximation. Since God's Number for $n=3$ is 26 (using quarter-turn metric), we can do:

$$ \frac{10000^2}{\log 10000} * \frac{\log 3}{3^2} * 26 = 34458757 $$

So to round off your question take that number, multiply it by 2.8s, and you get about 3.1 years.

$\endgroup$
  • $\begingroup$ +1. Since approximations are very loose anyway, this is a pointless nit-pick, but ... As mentioned in my comment, God's number counts moves; OP counts quarter turns. So, there's an additional "expected number of quarter turns" factor to consider. $\endgroup$ – Blue Jan 17 '19 at 2:15
  • $\begingroup$ How far off in either direction could this estimate be? Is it within an order of magnitude? $\endgroup$ – qazwsx Jan 17 '19 at 2:17
  • $\begingroup$ @qazwsx there is really no way to tell... $\Theta$ notation really only says what will happen in the limit... but before that it can deviate an arbitrary amount. $\endgroup$ – timidpueo Jan 17 '19 at 2:18
  • $\begingroup$ @Blue thx amended $\endgroup$ – timidpueo Jan 17 '19 at 2:22
  • 1
    $\begingroup$ The end of section 4 of that paper gives an explicit lower bound: an $n \times n \times n$ cube requires at least $$\frac{\left(\left\lfloor \frac{n}{2} \right\rfloor-1\right)^2}{\log_c (6n)} - 1$$ quarter-turns to solve, where $c=\frac{24!}{(4!)^6}$. For $n=10000$, this appears to work out to about $8 \cdot 10^7$ moves or a little over $7$ years. It looks like you could extract an explicit upper bound from the earlier bits of section 4 — it comes from an explicit solving algorithm — but it'd take more work. $\endgroup$ – Micah Jan 17 '19 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.