# $3 \times 3$ Rubik's cube scrambling question

It was proven that a Rubik's cube needs at most $20$ moves to solve. This implies that any configuration of a Rubik's cube can be reached from an unscrambled Cube in at most $20$ moves.

So, say when I scramble, I choose any move to do at random. Does this mean that it is useless to continue scrambling the cube after I do $20$ moves?

• What do you mean by "useless"? – timidpueo May 31 '14 at 5:47
• I guess that the goal in scrambling is to make every possible configuration equally likely, a "useless" move would be one that does not facilitate this (because this has already been reached) – MCT May 31 '14 at 5:49

If your intent, in scrambling, is to choose a position almost uniformly distributed among all possible positions, the a sequence of 20 randomly chosen moves is seriously inadequate. To illustrate, consider the much simpler system of permutations of 4 elements, where a move is defined as swapping 2 neighboring elements (for example, $1234 \rightarrow 1324$).

In this system, any position can be reached from any other in at most 6 moves. But if you scramble $1234$ (the "identity" permutation) the chance of reaching $4321$ is $\frac{4}{243}$, while uniform distribution would say the chance should be $\frac{1}{24}$.

Similarly in the Rubic group, 20-move scramblings at random will seriously under-represent the set of positions which are a distance of 20 from the identity.

• There may actually be only 1 position at a distance of 20 from the identity, called the superflip – NovaDenizen Aug 1 '14 at 17:00
• The superflip is one position requiring 20 moves, but cube20.org has a list of almost 100 million of them for download, with speculation that here are about 5 times as many in total. – Henning Makholm Feb 24 '17 at 20:57
• @NovaDenizen I think the superflip is one of three positions under the quarter-turn metric, where we count a half-twist (e.g. $F^2$) as two separate moves. See e.g. this cube20/qtm – Mark S Apr 14 at 13:49

The best way to select a permutation with a truly uniform distribution is to just pick a random integer between 1 and 43252003274489856000 and calculate that permutation.

If you want a convenient way to scramble a cube into an approximately random distribution then 25 to 30 moves will suit you. The official WCA scrambler uses 30 moves by default.

I think it's important to pick a random number of moves each time to smooth out some biases. Imagine you start on a white square on a chessboard then take 200 randomly chosen horizontal or vertical steps. You will never end up on a black square.

You already need 24 or 25 moves for the pocket cube (2x2x2) to be at a reasonably small distance from the uniform distribution (I made the exhaustive computation on computer - was unable to perform it for the much larger 3x3x3 space).

• Thomas your claim sounds cool! How were you able to exhaustively establish the above? Did you write all $6^{23}$ (resp. $6^{24}$) words of length $=24$ (resp. $=25$) with generating set $s=\langle F, F', U, U', L, L'\rangle$, and determine which element of $G$ each word corresponded to? What kind of computer did you use? – Mark S Apr 14 at 13:40