# Is there a “most random” state in Rubik's cube?

Is there a state in Rubik's cube which can be considered to have the highest degree of randomness (maximum entropy?) asssuming that the solved Rubik's cube has the lowest?

-
How do you define "most random"? Perhaps by the number of moves it takes to solve the cube? – Alex Becker May 28 '12 at 20:13
I don't know exactly what you mean by random, but you could consider a state that requires the most amount of moves to solve. – mrf May 28 '12 at 20:14
It is known that the maximum required number of moves is 20, but the state that requires 20 moves is not very "random" in the intuitive sense of random. – Rahul May 28 '12 at 20:30
I would suggest the interpretation of most randoms should be most probable number of moves to solve. The site Rahul Narain linked to says this is 18 moves from start. But no single position can be considered random. – Ross Millikan May 28 '12 at 21:51
You offer a bounty on this question, but you have yet to define what you mean by "most random". How can we possibly address your question? – Austin Mohr May 31 '12 at 1:46

Assuming 'most random' means 'takes the most number of moves to solve the cube', then the answer is 20. This site also has an example of a state that requires at least 20 moves to solve. This result is from 2010, and is a computer-assisted proof.

-
A state requiring $20$ can be described easily: the corner cubes are all correct, and the $12$ edge cubes are all on their correct edges but are all flipped. – Brian M. Scott May 28 '12 at 20:34
"a computer-assisted proof" is a bit of an understatement. IIRC, the computer doing the assistance was a $>1$ petaFLOP Google supercomputer, and even it took a while. – Alex Becker May 28 '12 at 21:23
It should be stated that this is with the half-turn metric (i.e. both quarter- and half-turns are allowed in the generating set and count for 1 turn). The quarter-turn metric is still unsolved and thought to be very hard compared to the half-turn metric AFAIK, and harder positions to solve than the superflip (which Brian described) are known. – Logan Maingi May 29 '12 at 20:36
@Brian, if that state has such a nice description, it cannot be called random, can it? :-) – lhf May 29 '12 at 22:35
nice point, another one definition of randomness for this problem --- the longest sentence to describe the state, kind of Kolmogorov complexity. – Yrogirg May 31 '12 at 6:28

Just as shuffling a deck of cards several times (say 7 or more) gives a very good approximation of a randomly chosen ordering of cards, mixing up a cube with 50 or 60 turns will give a very good approximation of a randomly chosen cube state.

A randomly chosen cube state might be what you want-- there is no single "most random" state. If there were, then in some sense, it wouldn't be very random; it would be very special! However, if you take a randomly chosen cube state, there's over a 99.75% chance it is at least 16 moves away from being solved; so we expect a randomly chosen cube to be very far away from a solved one.

Yes, it's possible to randomly mix up a cube and end up with something only a few moves from a solved cube, or even to end up with a perfectly solved cube. But the odds against it are astronomical. You could shuffle cards until the sun burns out (~5 billion years), and it's unlikely you would have put them back in order even once. Likewise, you could jumble the cube until the sun burns out, it's unlikely you'll just happen to solve the cube in all that time.

The nice thing about a randomly chosen state is that it's easy to approximate-- just randomly make turns for a while. I don't know how many turns you should do, I would guess 60 turns is plenty. I've seen people spend a long time, doing hundreds and hundreds of turns, trying to make the cube really hard to solve-- but all those extra turns don't accomplish much, it's still just another randomly chosen cube state, and we expect it to be just as hard to solve.

-
"I've seen people spend a long time, doing hundreds and hundreds of turns, trying to make the cube really hard to solve" -- Or perhaps they are just aware that humans are fairly lousy generators of randomness? When I try to just scramble a cube aimlessly, I tend to settle into repeated cycles of moves, and each move in such a cycle contributes much less randomness that an actual (equidistributed) randomly chosen move would have. – Henning Makholm May 31 '12 at 19:53
@HenningMakholm: Yes, that's possible. But I certainly don't know how to exploit such failures of randomness to solve the cube more quickly. In fact, even if you just use 15 or even 12 turns, I would start my cube-solving algorithm from scratch, and won't solve the cube any faster than usual, even though it's "closer" to a solved state than 99.75% of all cube states. – Jonas Kibelbek Jun 1 '12 at 0:51

If you're considering maximal entropy as I think your question alludes to, you need to maximize the degeneracy of the states since $S \equiv k \ln \Omega$, where $\Omega$ is the number microstates.

It doesn't make sense to consider a single state of the cube to be most random...we could just as well consider our chosen state to be "solved" and that would make it the least "random" in that sense. It makes more sense to consider an ensemble of cubes to be the most random state. In this case, the ensemble of cubes with the highest degeneracy is 18 moves away from being solved, with degeneracy of roughly 29 quintillion. [1]

-

There are many many positions that require 20 moves to solve, so I'd say the position that qualifies as "most scrambled" among them is the one that has fewest alternative paths to the sorted state. I have downloaded Herbert Kociemba's Cube Explorer (half-turn version) from http://kociemba.org/cube.htm and have been using it to track some 20-move positions. The position illustrated here was put to me by a Stephen Baxter (not me but an interesting coincidence of names) as requiring 25 moves. It doesn't, of course; it only needs 20. But Cube Explorer takes nearly two hours running on my quad-core 3.8 GHz AMD Windows 7 desktop to reduce its initial 21-move solution to one with 20 moves. The position with all 12 edges flipped ("superflip") solves to 20 much more quickly (26 seconds). I assume this is because the illustrated configuration has very few paths to a solution. So I think it has some claim to be at least one of the most scrambled positions.

I think there will always be more than one path to a solution, because (a) trivial differences such as the order of successive non-interfering moves such as FB or U2D', which could be executed as BF or D'U2; and because of the sheer number of possible 20-move sequences (18^20 = more than 12 septillion), which exceeds the number of configurations by a factor of some 294,000.

Baxter's "hard to solve" configuration doesn't look at all "random" as most people would intuitively think of the term; it has four regular pairs of top & bottom colours on the side faces, and on top and bottom faces the side-face-colour pairs are all a chess-knight's move apart.

-
Wouldn't the cube with the fewest minimum-lengtb paths to the solved cube be the already solved cube? – Deusovi May 25 at 4:25
Yes, but I'm dealing only with configurations requiring the maximum number of moves (20) to solve, and asking for which of these configurations is there only one (or possibly only a few) distinct solutions. – Steve B May 27 at 16:36