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$
2
  • $\begingroup$ What do you mean by "useless"? $\endgroup$
    – timidpueo
    Commented May 31, 2014 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$
    – MT_
    Commented May 31, 2014 at 5:49

3 Answers 3

Reset to default
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$
3
  • $\begingroup$ There may actually be only 1 position at a distance of 20 from the identity, called the superflip $\endgroup$
    – NovaDenizen
    Commented Aug 1, 2014 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$
    – hmakholm left over Monica
    Commented Feb 24, 2017 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
    Commented Apr 14, 2019 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
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$
1
  • $\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
    Commented Apr 14, 2019 at 13:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .