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

377 Views Asked by At

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?

3

There are 3 best solutions below

3
On

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.

1
On

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).

2
On

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.