Are there positions of the rubik cube which cannot be reached by applying the standard moves starting from the solved cube? If so, how many such positions are there?
Group Theory – Unreachable Rubik’s Cube Positions Explained
group-theoryrubiks-cube
Related Solutions
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.
As you can see by reading the answers to this question involving a knight tour on a chessboard, we can determine the expected return time for any irreducible Markov chain by finding the unique stationary distribution; if the mass of the distribution at a given state is $p$, then the expected return time to that state is $\frac{1}{p}$. (Intuitively, if we process the Markov chain for a long time, we expect to be at the given state with probability $p$, so the average distance between returns to the state is $\frac{1}{p}$.)
In the case of a random walk on a graph $G$, the unique stationary distribution is given by making the mass at each vertex proportional to its degree. When the graph is regular (as is the case here), each vertex will have the same mass, namely $\frac{1}{|G|}$. So the expected return time for each vertex will be exactly $|G|$.
Thus the expected number of turns required to get back to the starting state of any type of Rubik's cube is equal to the number of positions of the cube.
Best Answer
11 out of 12 random positions are unreachable.
This first part just looks at the positions of cublets, without regard to their orientation.
It is possible to place the corners in all $8!$ position permutations. Separately, it is possible to place all edge pieces in all $12!$ position permutations. But it is not possible to apply a permutation that swaps only two corners or two edges.
This is easily seen. All possible permutations arise from the application of 6 basic permutations corresponding to quarter-turns on each face. Each of these quarter-turns cycles 4 corners (an odd permutation, equivalent to 3 swaps, an odd number) and 4 edges (also an odd permutation). The combination of these two cycles is an even permutation (3+3=6 swaps, an even number), so any series of basic moves also results in an even permutation. This sets an upper bound of $\dfrac{8!12!}{2}$ position permutations.
It is possible to construct permutations that solely cycle the positions of 3 corners or 3 edges, so using these 3-cycles you can independendly reach all $\dfrac{8!}2$ even corner permutations and $\dfrac{12!}2$ even edge permutations, resulting in $\dfrac{8!12!}{4}$ total even position permutations. Turning one face throws both the corners and edges into odd permutations, and from here using the 3-cycle moves you can reach all $\dfrac{8!12!}{4}$ odd position permutations. Add these together and you get a lower bound of $\dfrac{8!12!}{2}$ reachable position permutations, which meets the upper bound.
In the second part here I'm talking about changing the orientations of the cubes, without changing their positions.
Corner rotations:
Moves exist that jointly counter-rotate any two corner pieces without affecting any other changes. This sets a lower bound of $3^7$ possible rotations of the corner pieces.
Consider a rotation labeling system for the corner cubes. Mark one facelet of each corner as special. Each corner cubelet position has a face whose normal points upward or downward, and call this position 0, the one clockwise from it 1, and the next clockwise 2. You will find that each basic move preserves the sum of these orientation numbers modulo 3, which sets an upper bound of $3^7$ possible corner orientations.
Edge rotations:
Move sequences exist that jointly flip any two edge pieces without affecting any other changes. This sets a lower bound of $2^{11}$ possible rotations of the edge pieces.
If you put together an arbitrary orientation numbering system like the corner orientation numbering system above, you'll find that all basic moves preserve the sum of orientations modulo 2. This sets an upper bound of $2^{11}$ possible rotations of the edge pieces.
So the cube in total has $\dfrac{8!12!2^{11}3^{7}}{2}$ permutations reachable through basic moves.
If you disassemble a cube you can place the corners in any of $8!$ position permutations and $3^8$ orientations, and the edges in any of $12!$ position permutations and $2^{12}$ orientations. This totals to $8!12!2^{12}3^{8}$ possible configurations, which means 11 out of 12 potential configurations are not reachable through basic moves.