4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you mean by "useless"? $\endgroup$ – timidpueo May 31 '14 at 5:47
  • 1
    $\begingroup$ 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) $\endgroup$ – MCT May 31 '14 at 5:49
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There may actually be only 1 position at a distance of 20 from the identity, called the superflip $\endgroup$ – NovaDenizen Aug 1 '14 at 17:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Feb 24 '17 at 20:57
  • $\begingroup$ @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 $\endgroup$ – Mark S Apr 14 at 13:49
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mark S Apr 14 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.