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?
Is there a "most random" state in Rubik's cube?
17
$\begingroup$
combinatorics
random
entropy
rubiks-cube
-
4How do you define "most random"? Perhaps by the number of moves it takes to solve the cube? – 2012-05-28
-
0I don't know exactly what you mean by *random*, but you could consider a state that requires the most amount of moves to solve. – 2012-05-28
-
0Even most amount of moves might be hard. You would need to know a 'most efficient' algorithm. – 2012-05-28
-
9It is known that [the maximum required number of moves is 20](http://www.cube20.org/), but the state that requires 20 moves is not very "random" in the intuitive sense of random. – 2012-05-28
-
2I 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. – 2012-05-28
-
0@johnw. There are optimal algorithms which are computationally useful, and have been since at least 2006. The one I use on my 10-year-old laptop rarely takes more than an hour on random positions, but it seems no one can prove that the algorithms are much better than brute-force searching in the worst-case. – 2012-05-29
-
6You 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? – 2012-05-31
-
0The 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