11
$\begingroup$

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!

  • 1
    @FUZxxl, I was going to give the same links, basically what that means is that people do not know how to mathematically show that it must be 20, but they have shown it using brute force!2011-04-12

1 Answers 1

17

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).