The 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. The algorithm of God 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 problems). The number of gods, respectively, is defined as the number of moves required by this algorithm at worst. So, for the Rubik's Cube, this number is 20.
The cube itself was invented in 1974. Theoretical studies of the cube focused on the evaluation of the lower and upper bounds of the maximum number of moves to solve the cube.
')
By 1980, the lower bound was estimated as 18: significantly different sequences of moves 17 or less in length were less than cube configurations. This estimate lasted for 15 years - until 1995, when Michael Reid proved that a superflip (correct corners and mixed middle sides) needs exactly 20 moves to configure.
Meanwhile, the upper bound estimate was falling more often, but more slowly: in 1981 it was 52, in 1995 the same Michael Reid received a value of 29, in 2008 Tomas Rokicki reduced it to 25-23-22 (23 turn) won an article on Habré :-)), and finally, in July 2010, the same Tomasz Rokitski along with Morley Davidson, John Dethridge and Herbert Kociemba got the final result - 20 moves.
There are a total of 8! * 3 7 * 12! * 2 10 = 43,252,003,274,489,856,000 ~ 4.3 * 10 19 cube configurations. Using symmetries and covering sets, they boiled down to 55,882,296 essentially different configurations that had to be honestly solved. To simplify the task for each configuration, we were looking not for the optimal solution (it’s also God's solution), but for 20 or less moves.
Finally, the configurations were distributed across multiple Google computers, and the calculations were 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 in its finality, since neither the upper nor the lower bound can be moved further. A well-known (and you yourself were addicted to the cube?) The open problem is solved, you can congratulate the researchers and switch to something else.
It's funny that many people who learn about this result, reproachfully expressed in the sense that Google has nowhere to go computing power, which can solve the problem of cancer. Well, if someone can really find cancer treatment in just 35 CPU years (and several years of his work), I think Google will gladly give them one.
1. God's Number is 20
2. Rubik's Cube on Wikipedia
3. Discussion news on reddit
A bit of history
The cube itself was invented in 1974. Theoretical studies of the cube focused on the evaluation of the lower and upper bounds of the maximum number of moves to solve the cube.
')
By 1980, the lower bound was estimated as 18: significantly different sequences of moves 17 or less in length were less than cube configurations. This estimate lasted for 15 years - until 1995, when Michael Reid proved that a superflip (correct corners and mixed middle sides) needs exactly 20 moves to configure.
Meanwhile, the upper bound estimate was falling more often, but more slowly: in 1981 it was 52, in 1995 the same Michael Reid received a value of 29, in 2008 Tomas Rokicki reduced it to 25-23-22 (23 turn) won an article on Habré :-)), and finally, in July 2010, the same Tomasz Rokitski along with Morley Davidson, John Dethridge and Herbert Kociemba got the final result - 20 moves.
How?
There are a total of 8! * 3 7 * 12! * 2 10 = 43,252,003,274,489,856,000 ~ 4.3 * 10 19 cube configurations. Using symmetries and covering sets, they boiled down to 55,882,296 essentially different configurations that had to be honestly solved. To simplify the task for each configuration, we were looking not for the optimal solution (it’s also God's solution), but for 20 or less moves.
Finally, the configurations were distributed across multiple Google computers, and the calculations were 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 in its finality, since neither the upper nor the lower bound can be moved further. A well-known (and you yourself were addicted to the cube?) The open problem is solved, you can congratulate the researchers and switch to something else.
It's funny that many people who learn about this result, reproachfully expressed in the sense that Google has nowhere to go computing power, which can solve the problem of cancer. Well, if someone can really find cancer treatment in just 35 CPU years (and several years of his work), I think Google will gladly give them one.
Sources
1. God's Number is 20
2. Rubik's Cube on Wikipedia
3. Discussion news on reddit
Source: https://habr.com/ru/post/101361/
All Articles