22
$\begingroup$

Suppose, random moves are made to solve Rubik's cube. A move consists of a $90$-degree-rotation of some side. The starting position is also random.

  • What is $E(X)$, where $X$ is the number of moves until the cube is solved ?
  • How many moves must be made, that the probability that the cube is solved, exceeds $99$% ?
$\endgroup$
  • 1
    $\begingroup$ I assume you mean the probability that the cube has been solved before move $n+1$ for the second question. I hope you get an interesting answer! $\endgroup$ – Mark Bennet May 10 '15 at 21:13
  • $\begingroup$ Souldn't the answer to the first be simply: the order of the group? $\endgroup$ – Hagen von Eitzen May 10 '15 at 21:16
  • 1
    $\begingroup$ @HagenvonEitzen Since the moves are restricted to a set of generators, doesn't that make a difference? It seems to me that the answer would be the order of the group only if you could make an arbitrarily complex move each time (i.e., one that was a combination of several $90^\circ$ rotations). $\endgroup$ – Théophile May 10 '15 at 21:26
  • 1
    $\begingroup$ @Théophile You are right. I made the calculation with $S_3$ and generators $(1\,2),(2\,3)$: $E(X)=5.8\overline 3$ instead of $6$. With $S_4$ and generators $(1\,2),(1\,2\,3\,4)$: $E(X)\approx 28.82$ instead of $24$; with a third generator $(4\,3\,2\,1)$: $E(X)\approx 32.09$. We can expect $E(X)$ to become larger than $|G|$, the more relations there are among the generators, I suppose $\endgroup$ – Hagen von Eitzen May 11 '15 at 13:42
  • 1
    $\begingroup$ This seems question is mirrored on mathoverflow: mathoverflow.net/questions/115178/… $\endgroup$ – Drunk Cynic Dec 21 '15 at 0:32
1
$\begingroup$

Each edge has 2 faces, providing for $12!\times 2^{12}$ possibilities.

Each vertex has 3 faces, providing for $8!\times 3^8$ possibilities.

Therefore if you dismantle the cube it can be reassembled in 519,024,039,293,878,272,000 possible states.

Thanks to Gerry Myerson for this: According to Singmaster's Notes on Rubik's Magic Cube, the total permutation of the edge and vertex cubes must be even. Then, if you orient all but one of the edges, the remaining one is forced, and similarly for the vertices, so only 1 in 12 possible assemblies of the cube is actually a "solvable" or "arrivable at by rotation" state.

Dividing the above number by 12 therefore confirms Turner and Gold's result (which i haven't seen first hand) that the number of states "arrivable at by rotation" is $43,252,003,274,489,856,000$.

Therefore any given random move has probability $1/43,252,003,274,489,856,000$ of completing the cube.

For such high $n$ the binomial will approximate the normal distribution, so the expected number of moves will be the mean.

I think Wolfram Alpha struggled with the number-crunching in my last answer so I've solved by substitution:

$0.5=\binom{n}{0}p^0q^n$ where $q=(1-1/43,252,003,274,489,856,000)$

$0.5=(1-1/43,252,003,274,489,856,000)^n$

$n\approx 3×10^{19}$ moves is the expected number of moves to solve it.

Repeating the substitution for 0.01:

$n\approx 1.992*10^{20}$ moves is the expected number of moves to reach 99% confidence.

Use of the binomial in this answer makes the technically incorrect assumption that the probability of solving on any particular move is not related to the probability of solving on a move n steps earlier. (i.e. there is no serial correlation). However as an experienced cube user I know that the cube very quickly diverges from its current position given random movements and therefore the effect of serial correlation will be very low.

This divergence is clearly illustrated by the fact that it follows from Rokicki, Kociemba, Davidson, and Dethridge's 2010 result that it takes at most 20 Singmaster moves to take the cube to any obtainable state you wish. Contrast that 20 moves with the expected number of random moves to solve the cube and you get an idea how minimal serial correlation will be.

$\endgroup$
  • $\begingroup$ Feel free to correct the $3\times 10^{19}$ number to $2.16\times 10^{19}$ if you know this to be true. I had some problems with the number crunching, it seems likely the mean number of moves is exactly half the inverse of the probability of solving on any random move but I forget my binomial distribution rules (it is 25 years!) $\endgroup$ – user334732 May 22 '16 at 10:30
-1
$\begingroup$

The center squares of each face don't actually move independently of each other, they rotate but since each orientation of that square is indistinguishable its the other three, there are $4^6= 32,768$ acceptable finished solutions to the cube, not just 1, considering only the permutations of the pieces relative to each other, which is perhaps not obvious to everybody.

Once solved it can also be held with a choice of 6 faces facing the floor and each of those can be rotated into 4 unique positions, making, depending how you permutate your possibilities, 786,432 possible "correct" solutions.

To eliminate this, if we fix the axes and the centre-faces, which is governed by the manufacturing of the cube anyway, hold one face to the floor, don't rotate any centre squares and don't move any of the axes, we're left with 12 "edges cubes" and 8 "vertex cubes".

Each edge has 2 faces, providing for $12!\times 2^{12}$ possibilities.

Each vertex has 3 faces, providing for $8!\times 3^8$ possibilities.

Therefore ignoring the for all intents and purposes identical, centre squares and orientations of the cube, the cube has 519,024,039,293,878,272,000 possible states.

The probability of solving it on any given random move is therefore 1 in 519 billion billion.

Achieving a probability of $99\%$ is therefore a simple binomial probability... and you may have to correct this bit as it's 25 years since I did maths:

Our desired result is most simply thought of as the probability of "not having no successes", i.e. $1-P(x=0)$

$0.99=1-\binom{n}{0}p^0q^n$ where $q=(1-1/519024039293878272000)$

$0.01=(1-1/519024039293878272000)^n$

$n=6.4812×10^{14}$ moves, which I'm reliably informed by Wolfram Alpha is 32 moves per red blood cell in your body.

I should add to this answer that it is of course fatally flawed in that it makes no allowance for the fact that the positions of the cube are serially correlated and therefore if one starts in a position which is "more distant" from complete, it is more likely one will cycle repeatedly through those distant permutations than move through permutations having an average likelihood of success.

This has the effect of making "fast" solutions faster on average and "slow" solutions slower than the binomial estimator and therefore the 99% confidence interval, being a distant interval, will typically take a little longer than the $6.4812\times 10^{14}$ moves estimated. However if you require an accurate answer which makes allowance for that, I suspect you will be waiting for a very long time!

This approximating a normal distribution for large $n$, the estimated number of moves required to solve it will be approximately half of the 99% interval, say $3.2\times 10^{14}$ moves.

$\endgroup$
  • $\begingroup$ Sorry I just realised you also asked for E(X) which I'm guessing is an unbiased estimator of the number of moves it will take. Give me a chance to look up the unbiased estimator of the binomial and I will add it to my answer. $\endgroup$ – user334732 May 21 '16 at 19:25
  • $\begingroup$ With such a low $p$ and a high $n$, this is going to approximate a very wide and low normal distribution. $\endgroup$ – user334732 May 21 '16 at 19:31
  • $\begingroup$ Ok i've put in a quick estimator for the number of moves to solve. The numbers for the binomial look too small but that's what Wolfram Alpha is giving me. Please feel free to edit and correct. $\endgroup$ – user334732 May 21 '16 at 20:27
  • $\begingroup$ Very interestingly for this problem (and fortunately for a basic mathematician like me!), every possible move of the cube involves rotating 4 vertex cubes and 4 edge cubes relative to the remaining 16 movable cubes and as such the movement of every square is equally probable regardless of its type and as such the binomial method is equally strong to the (beautifully elegant) but unnecessarily complex methods based on rotation groups. $\endgroup$ – user334732 May 21 '16 at 20:36
  • $\begingroup$ Actually, one final thought... There is a possible flaw in my answer in that it assumes that there is not some arrangement of the parts of the cube that is only attainable by dismantling and reassembly - a possibility which the rotation group method will not suffer from. $\endgroup$ – user334732 May 21 '16 at 20:46

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.