# Solving a scrambled $3 \times 3 \times 3$ Rubik's Cube with at most 20 moves!

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!

-
The proof about the diameter of the Rubik's cube graph is mathematical. – Arturo Magidin Apr 12 '11 at 15:09
I would suggest looking on Wikipedia And also here – FUZxxl Apr 12 '11 at 15:29
@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! – picakhu Apr 12 '11 at 15:42

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