17
$\begingroup$

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?

  • 0
    The idea of maximal entropy is valid. It was first proposed (as far as I know), by Douglas Hofstadter in GEB. I've never tackled the problem completely, but I even imagined to find an algorithm diminishing the entropy until solved. I realized that the cube can be in local minima that are not solved, i.e., whatever side you turn, the entropy will increase. -- A similar question was asked here (forums.xkcd.com/viewtopic.php?t=86624), but no answer was forthcoming. -- Here you can find a genetic algorithm approach with a download. francocube.com/cyril/genetic_alg.2017-07-08

5 Answers 5

12

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.

  • 1
    The quarter-turn metric has since been solved; God's number is 26 qt. More interestingly, unli$k$e the HTM case, there is exactly one state that is 26 qt away from solved: Superflip composed with 4-spot.2015-03-28
5

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.

  • 2
    @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.2012-06-01
2

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]

2

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.

  • 0
    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.2016-05-27
0

I feel like a "most randomized cube" state that this question is asking if one where the least number of individual blocks one each side are In the correct position. Not necessarily one that takes a lot of moves to solve, but where the most amount of blocks need to be moved for it to be solved. I think that's a better, and more productive for the purpose of conversation, definition then the amount of turns because that has sort of hit a conversation dead end.

  • 0
    It is easy to create a not-at-all-random state where _every_ cubie is in a wrong position -- e.g. $U^2D^2R^2L^2$.2016-10-23