Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
