August 10, 2010 at 11:41The number of god for the Rubik's Cube is 20
There are many algorithms that collect the Rubik's Cube - more or less efficiently. Those that the average mortal can learn and use usually require more than 40 moves. God’s algorithm is an algorithm that uses the minimum number of moves to build any initial configuration (the term is associated with the concept of omniscience and is also used for a number of other mechanical and logical tasks). The number of god, respectively, is defined as the number of moves required by this algorithm in the worst case. So, for the Rubik's Cube, this number is 20.
The cube itself was invented in 1974. Theoretical studies of the cube focused on assessing the lower and upper boundaries of the maximum number of moves to solve the cube.
By 1980, the lower bound was estimated as 18: significantly different sequences of moves of length 17 or less turned out to be less than the configurations of the cube. This assessment lasted 15 years - until 1995, when Michael Reid proved that for the “superflip” configuration (the right corners and the confused midpoints of the sides) exactly 20 moves are needed.
Meanwhile, the upper bound estimate decreased more often, but more slowly: in 1981 it was 52, in 1995 the same Michael Reid got a value of 29, in 2008 Tomas Rokicki reduced it to 25-23-22 (an estimate of 23 moves awarded the article on Habré :-)), and finally in July 2010 the same Tomasz Rokicki, along with Morley Davidson, John Dethridge and Herbert Kociemba, got the final result - 20 moves.
There are 8 in total! * 3 7 * 12! * 2 10 = 43,252,003,274,489,856,000 ~ 4.3 * 10 19 cube configurations. Using symmetries and covering sets, they were reduced to 55,882,296 essentially different configurations, which had to be honestly solved. To simplify the task for each configuration, they did not look for the optimal solution (it is the solution of God), but a solution in 20 or less moves.
Finally, the configurations were distributed among many Google computers, and the calculations completed in just a few weeks. On a good computer (Intel Nehalem, four-core, 2.8GHz) these calculations would take 1.1 billion seconds, or 35 years.
Although many criticize the Rubik's Cube for the lack of practical value, the result is still interesting - at least for its finality, since neither the upper nor the lower boundary can be moved further. The well-known (and you yourself were fond of the cube?) Open problem has been solved, you can congratulate the researchers and switch to something else.
It's funny that many people who learn about this result are reproachfully saying that Google has nowhere to put the computing power that can solve the cancer problem. Well, if someone can really find a cancer treatment in just 35 CPU-years (and several years of his work), I think Google will be happy to give them them.
1. God's Number is 20
2. Rubik's Cube on Wikipedia
3. Discussion of news on reddit
A bit of history
The cube itself was invented in 1974. Theoretical studies of the cube focused on assessing the lower and upper boundaries of the maximum number of moves to solve the cube.
By 1980, the lower bound was estimated as 18: significantly different sequences of moves of length 17 or less turned out to be less than the configurations of the cube. This assessment lasted 15 years - until 1995, when Michael Reid proved that for the “superflip” configuration (the right corners and the confused midpoints of the sides) exactly 20 moves are needed.
Meanwhile, the upper bound estimate decreased more often, but more slowly: in 1981 it was 52, in 1995 the same Michael Reid got a value of 29, in 2008 Tomas Rokicki reduced it to 25-23-22 (an estimate of 23 moves awarded the article on Habré :-)), and finally in July 2010 the same Tomasz Rokicki, along with Morley Davidson, John Dethridge and Herbert Kociemba, got the final result - 20 moves.
How?
There are 8 in total! * 3 7 * 12! * 2 10 = 43,252,003,274,489,856,000 ~ 4.3 * 10 19 cube configurations. Using symmetries and covering sets, they were reduced to 55,882,296 essentially different configurations, which had to be honestly solved. To simplify the task for each configuration, they did not look for the optimal solution (it is the solution of God), but a solution in 20 or less moves.
Finally, the configurations were distributed among many Google computers, and the calculations completed in just a few weeks. On a good computer (Intel Nehalem, four-core, 2.8GHz) these calculations would take 1.1 billion seconds, or 35 years.
Reaction
Although many criticize the Rubik's Cube for the lack of practical value, the result is still interesting - at least for its finality, since neither the upper nor the lower boundary can be moved further. The well-known (and you yourself were fond of the cube?) Open problem has been solved, you can congratulate the researchers and switch to something else.
It's funny that many people who learn about this result are reproachfully saying that Google has nowhere to put the computing power that can solve the cancer problem. Well, if someone can really find a cancer treatment in just 35 CPU-years (and several years of his work), I think Google will be happy to give them them.
Sources
1. God's Number is 20
2. Rubik's Cube on Wikipedia
3. Discussion of news on reddit