Google cracks Rubik's Cube by proving only 20 moves are ever needed to solve it

Scientists have proved that you only need 20 moves to solve the Rubik's Cube

It is a figure that will leave veteran Rubik’s Cube addicts shaking their heads in disbelief.

But scientists have worked out that the famous puzzle can always be completed in 20 moves or less.

Using Google’s supercomputers, a team of researchers have processed every one of the Rubik’s Cube’s 43,252,003,274,489,856,000 different configurations to work what is the maximum number of moves needed to complete it.

Scientists have long believed that 20 was the so-called ‘God number’ in theory but it has been impossible until now to find the processing power to prove it definitively.

Only 300 million configurations, a tiny fraction of the total, require 20 moves. The majority needed only between 15 and 19 moves.

Professor Morley Davidson, a mathematician from Ohio’s Kent State University, worked alongside an engineer at Google and colleagues from Germany and California.

He said that it would have been ‘completely hopeless’ to try and test every configuration individually so instead the team split the combinations into 2.21 billion groups of 20 billion positions.

The team then used symmetry to reduce the number of problems down still further.

The researchers explained on their website: ‘If you take a scrambled Cube and turn it upside down, you have not made it any more difficult; it will still take the same number of moves to solve.



‘Instead of solving both of these positions, you can simply solve one, and then turn the solution upside down for the other.’



Moves required to solve Rubik's Cube

Number 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,24

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



A table which shows the number of different Rubik's Cube configurations and how many moves are needed to solve them. The majority of configurations need only 18 moves to complete



Each of these individual problems were small enough to fit into the memory of a standard PC and the way the algorithms broke the sets down meant each could be solved in less than 20 seconds.

To solve the maximum moves needed would have taken a standard desktop PC around 35 years to solve but it took the team only a few weeks using Google’s supercomputers.

The magic figure of 20 is known as ‘God’s Number’ because it refers to the most efficient algorithm for solving a puzzle that always uses the shortest sequence of moves.

Since the very earliest days of the Rubik’s Cube scientists have been trying to work out the maximum number of moves needed to complete it.

In 1992 Hans Kloosterman managed to prove that 42 moves was the maximum required, while in April 2006 Silviu Radu had improves this to 27 moves.

The Rubik's Cube was invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik but was not released until 1980 when it became a phenomenon.

Scotsman Breandan Vallance, 18, is the current world Rubik’s Cube champion with an average solving time of an astonishing 10.74 seconds.

