How can I obtain or sample a random Rubiks Cube shuffle?

Question

I was thinking of how to obtain a random shuffle of the Rubik's cube with uniform probability.

• Simply trying a randomly generated sequence of turns will not necessarily produce a uniform distribution on the final states!

• Alternatively, one could break the cube and reassemble it piece by piece with uniform probability for which piece to put next and in which orientation. Then the cube has a probability of 1/12 of being solvable, so we'd need to reject an expected 11 configurations before we obtain one that's solveable. (This can be checked with known parity checks on the edges and on the corners.)

Is there anything more efficient than this?

• One idea I had could use Metropolis Hastings - if we treat the shuffles of the cube as a graph, then each vertex has degree 12 (single turn metric) or 18 (HTM). But I think that in this case, we would never reject any samples - and so all we are left with is the statement that if we keep randomly applying moves to the cube, the probability distribution we obtain converges to the uniform distribution. A back of the envelope calculation suggests (please correct me if I'm wrong?) that if $N = 4.3*10^{19}$ is the number of valid Rubik's cube shuffles, then we should aim for more than $\frac{\ln{N}}{\ln{12}} \approx 19$ (STM) or $\frac{\ln{N}}{\ln{18}} \approx 16 (HTM)$ turns.

Is there a way to precisely sample a shuffle of a Rubik's Cube with a finite number of steps?

Answer 1

Represent the group of rotations as a permutation group. From a stabilizer chain you can generate uniformly distributed random elements.

Stabilizer chains are the standard data structure for algorithms with permutation groups, you can find a description for example in my lecture notes https://www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf

Answer 2

Method 2 can easily be tweaked to only produce solvable scrambled cubes. Simply make sure that whenever you place a piece in such a way that it violates a constraint, you take it out again and fix it.

• First mix the 12 edge pieces in any order and orientation, and reassemble them into the cube. If the edge flip constraint is violated, flip the last edge piece you placed (which can be assumed without loss of generality to be the piece at location UF).

• Mix the 8 corner pieces in any order and orientation, and reassemble them into the cube. If the permutation parity constraint is violated, swap the last two corner pieces you placed (which can be assumed without loss of generality to be the piece at location URF and ULF). If the corner twist constraint is violated, rotate the last corner piece you placed (which can be assumed without loss of generality to be the piece at location URF).

In other words, randomly assemble the cube. If permutation parity is violated, swap the pieces at URF and URL. If edge flip is violated, flip the edge at UF. If corner twist is violated, twist the corner at URF.

It is easy to see that this produces a uniform distribution, because every valid cube position is the result of any of exactly 12 randomly assembled cubes, and you are essentially choosing one of the randomly assembled cubes uniformly.