[Math] Solving a scrambled $3 \times 3 \times 3$ Rubik’s Cube with at most 20 moves!

combinatoricsrecreational-mathematicsrubiks-cube

I read somewhere that any scrambled form of $3 \times 3 \times 3$ Rubik's cube can be solved using at most $20$ moves, and I just said "wow"! I am wondering can we prove this by mathematical ways? Or this is just solvable by computers? I do not know even how to think about such a problem, so please tell me if you have any information about it.

[Also, I read an article about solving a $n \times n \times n$ cube! it was interesting…just as a suggestion: think to find a method for solving a given scrambled $n \times n \times n$ Rubik's cube.]

P.S. you can see here for some information about Rubik's cube and its moves.

Thanks!

Best Answer

Yes, the result is very mathematical, though computers were used for many of the calculations. Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge proved this result in July 2010 and put up a very nice webpage at cube20.org, with some history of the problem and their basic methods.

The team consisted of a programmer, a math teacher, a mathematician, and an engineer. There are two parts to the problem: find a method that lets you solve any cube in M moves or less, and find a really hard starting position, that takes at least N moves to solve. These are upper and lower bounds for the problem-- the goal is to keep finding better methods for solving cubes, or to keep finding tougher starting positions, until you can show M=N.

In 1981, it was known that some positions took at least 18 moves, and Morwen Thistlethwaite had a method to solve any cube in 52 moves or less. The website lists the progress over the last few decades, narrowing in on the number 20. Part of the progress comes from having more powerful computers to work with, but a lot of it is having a better idea (math!) to simplify the problem.

Here's a cool table (copied straight from cube20.org) showing how many starting positions require 20 moves, 19 moves, 18 moves, etc. You can see there are many, many starting positions; and it's actually really tough to find one that takes 20 moves to solve.

   Distance Count of Positions

   0        1
   1        18
   2        243
   3        3,240
   4        43,239
   5        574,908
   6        7,618,438
   7        100,803,036
   8        1,332,343,288
   9        17,596,479,795
   10       232,248,063,316
   11       3,063,288,809,012
   12       40,374,425,656,248
   13       531,653,418,284,628
   14       6,989,320,578,825,358
   15       91,365,146,187,124,313
   16       about 1,100,000,000,000,000,000
   17       about 12,000,000,000,000,000,000
   18       about 29,000,000,000,000,000,000
   19       about 1,500,000,000,000,000,000
   20       about 300,000,000

As for bigger cubes, there are many methods for solving bigger cubes already. It's actually not that much tougher than solving the 3x3x3 cube; it just takes longer. But I don't think many people will work on finding the optimal number of moves for bigger cubes-- it will be much harder (probably not possible with current computers) and is not as interesting (because everyone cares most about the 3x3x3 cube).

Related Question