# Number of moves necessary to solve Rubik's cube by pure chance

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$% ?
• 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! May 10, 2015 at 21:13
• Souldn't the answer to the first be simply: the order of the group? May 10, 2015 at 21:16
• @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). May 10, 2015 at 21:26
• @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 May 11, 2015 at 13:42
• This seems question is mirrored on mathoverflow: mathoverflow.net/questions/115178/… Dec 21, 2015 at 0:32

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.

• 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!) May 22, 2016 at 10:30

The answer to your first question is a little bit more than the number of possible cube configurations (maybe 25% more). Since a 3x3x3 cube has roughly 43 quintillion configurations, I would estimate it would take around 54 quintillion random moves to get to a solved state in expectation.

To explain how I got here, instead consider the question "if I picked a position from random, what is the expected number of picks until I get the solved state?" It's the same as rolling a (very very) large die numbered 1 to the number of cube configurations. And then counting how many rolls it would take to roll a 1. The answer to this question is, in expectancy, it would take the number of cube configurations (around 43 quintillion).

Your first question is similar to my question, except instead of jumping around to random positions, you can only go one turn at a time. Which means it's relatively likely you will step to a new position, and then randomly step back to that original position. This makes the process for your question "less random" than my question. This means that the answer to your question will be greater than the number of cube configurations.

The good news is, it's still pretty random. What I mean by that is if you take a cube, and randomly do (say) 100 moves, you'll end up in a sufficiently random position. I don't have any formal definition for "sufficient" or why that is true... I'm just going off of my intuition as a cube solving hobbyist, and also the fact that God's Number is 20. This means that the answer to your question won't be MUCH greater than the number of cube configurations (I personally estimate around 25% greater).

I believe the exact answer to your question is hard to get. Here is a Mathologer video asking exactly your question, but not answering it! (In the video, he estimates the value for a 2x2x2 cube. This is what I based my 25% guess off of.) In the video, he calls the answer you seek the Monkey Number of the Rubik's cube. The question he DOES answer, however, is "what is the expected number of moves to get to a solved state, if you start from a solved state?" Here, he gives quite an ingenious proof, and the answer turns out to be exactly the number of cube configurations.

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.

• 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. May 21, 2016 at 19:25
• With such a low $p$ and a high $n$, this is going to approximate a very wide and low normal distribution. May 21, 2016 at 19:31
• 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. May 21, 2016 at 20:27
• 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. May 21, 2016 at 20:36
• 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. May 21, 2016 at 20:46