By Masakazu "Matto" Matsumoto from Nagoya, Japan (http://flickr.com/photos/vitroids/1527092475/) [CC BY 2.0 (http://creativecommons.org/licenses/by/2.0)], via Wikimedia Commons

What are the odds of solving a Rubik’s cube by making random moves?

Short answer: Depends how many moves you make.

Long answer: “God’s Number” is 20. This is the minimum number of moves needed to solve any Rubik’s cube. That means that for any possible configuration of a cube, it takes exactly twenty moves or less to solve it. This was proved by the Cube20 team in 2010 [1].

 

rubikscubedistances

Reproduced from Cube20.org

This result tells us something interesting – while the Rubik’s cube has 43,252,003,274,489,856,000 possible configurations, we can classify each configuration by the minimum number of moves it takes to solve it. The Cube20 team call this the ‘distance’ of the configuration. They make an interesting observation about distance-20 positions, they “are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions.” Such is the power of big numbers.

 

Take a look at the table to right. Of the 43 quintillion possible configurations, more than two-thirds of them are at distance-18, and the overwhelming majority of configurations are between distance-15 and 20.

 

So what if you picked up a random Rubik’s cube? Literally random. This cube is completely scrambled so that it is equally likely to be any one of the possible configurations. The odds are decent that it will be a distance-18 configuration. So what are the odds that you could make 18 random moves in a row and have a solved cube in your hand? To figure this out, we need to know how many possible moves there are.

 

Since there are 6 faces, each of which can be turned 1, 2, or 3 steps (4 steps returns it to the original position), there must be 6*3=18 possible moves. This agrees with the table; there are 18 possible distance-1 configurations. So if we make 18 random moves, then our odds of having a solved cube at the end will be 1 in 1818. As a percentage, this is 0.000000000000000000000025%. This is so abysmally small that if anyone ever told me that they solved a Rubik’s cube on ‘accident’ that I wouldn’t believe them.

 

But what if we kept making moves? How many moves would we have to make before the odds start to become good that we’ll get a solved Rubik’s cube?

In statistical physics, we have the ‘ergodic hypothesis‘ which says that any given configuration of a statistical system is equally likely, and that if you wait long enough eventually the system will pass through every possible state. This is useful for something like a collisional gas in kinetic theory – if you let them rattle around long enough each particle will eventually visit every spot in the box.

Greg L at the English language Wikipedia [GFDL (http://www.gnu.org/copyleft/fdl.html) or CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0/)], via Wikimedia Commons

If you wait long enough, the odds are good that every particle will visit every possible space in the box.

This wouldn’t be relevant to a Rubik’s cube where you use an algorithm, but a Rubik’s cube making random moves is exactly the sort of ‘random walk’ that the ergodic hypothesis applies to. All we have to do is make enough moves that the Rubik’s cube is likely to have been in every possible configuration.

This might seem weird to you, but remember that all configurations of the cube are equally likely. There’s nothing special a priori about the configuration where each side is the same color- we could peel off the stickers, label the cubes with random letters or numbers, and designate that configuration as the solution.

This trick is kind of like shuffling a deck and finding all the cards ordered by suit and value. While unlikely for any given shuffle, it has the exact same probability as any other ‘disordered’ arrangement! It’s simply highly unlikely because ‘disordered’ arrangements outnumber the ‘ordered’ arrangements by a huge margin., but if you shuffle the deck enough times it’ll happen sooner or later.

If there are 43 quintillion configurations of the cube, then I’d suggest making at least that many moves in order to get good odds of any one specific configuration occurring. To get really good odds, I’d suggest making 1818 moves – this means that almost every possible set of 18 sequential moves will occur, and so sooner or later it’ll have to hit the solved configuration.

If you have a Rubik’s cube at home that you don’t know how to solve, this might not be the best way to go about it. If you could make 1 move per second, it would take you a quadrillion years to solve this cube, which is 100,000 times the age of the universe. It might just be easier to ask your smart friend for help.

 

 


 

 

image credit: Wikimedia Commons and cube20.org

 


 

 

Have a question? Send it to matt@quarksandcoffee.com