How many turns are needed to restore the Rubik's Cube?

The Rubik's Cube is a popular educational toy that has been popular all over the world since the early 1980s.

The Rubik's Cube has many ways to play, including speed racing, blind solving, and single solving. Its popularity has lasted for a long time, and large and small competitions are held every year. It is one of the most popular intellectual games.

The Rubik's Cube in the usual sense refers to the three-dimensional Rubik's Cube in a narrow sense. The three-dimensional Rubik's Cube is usually a cube and is made of elastic hard plastic. The conventional racing method is to scramble the Rubik's Cube and then restore it in the shortest time. The Rubik's Cube in a broad sense refers to all kinds of geometric objects that can be scrambled and restored by rotation.

The Rubik's Cube, Huarong Road and French Single Noble (Independent Diamond Chess) are known as the three wonders of the intellectual game world.

Image source: pexls

The Rubik's Cube was invented by Ernö Rubik, a professor of architecture at the Academy of Applied Arts in Budapest, Hungary, and is also known as the Rubik's cube.

Image source: pexls

Rubik originally wanted to invent not an educational toy, but a teaching tool that could demonstrate spatial rotation and help students intuitively understand spatial geometry. After a period of consideration, he decided to make a 3×3×3 cube composed of small blocks, each face of which could be rotated at will.

Image source: pexls

Since 1981, Rubik's Cube enthusiasts have started to hold Rubik's Cube competitions around the world. In these competitions, players continue to break the world record for the shortest recovery time.

However, the number of rotations used by players to restore the Rubik's Cube is not the theoretical minimum number (that is, it is not "God's number"), because they use a method that is easy for the human brain to master and pursue the shortest restoration time.

Although a few more rotations take a little longer, it is still much faster than finding the theoretical minimum number of rotations - in fact, the latter is often simply beyond the human brain's ability to perform.

So, how many turns are needed to restore the Rubik's Cube? Or to be more precise, how many turns are needed to ensure that any color combination of the Rubik's Cube can be restored? This question not only makes Rubik's Cube enthusiasts curious, but also arouses the interest of some mathematicians because it is a difficult mathematical problem. Mathematicians even gave this minimum number of turns a very impressive nickname, called "God's number".

Since the 1990s, mathematicians have been looking for this mysterious "God's number". One of the most direct ideas for finding the "God's number" is something that everyone can think of, which is to calculate the minimum number of rotations for all color combinations one by one. The largest one among them is obviously the minimum number of rotations that can ensure that any color combination is restored, that is, the "God's number". Unfortunately, such calculations are beyond the reach of the world's most powerful computers, because there are too many color combinations in the Rubik's Cube. What to do? Mathematicians had to resort to their old profession - mathematics. In 1992, a German mathematician named Herbert Kociemba proposed a new idea. He found that among the basic rotation methods of the Rubik's Cube, there is a part that can form a series by itself, and through this part of the rotation, nearly 20 billion color combinations can be formed. Using these 20 billion combinations, Kosenba broke down the Rubik's Cube restoration problem into two steps: the first step is to transform any color combination into one of the 20 billion combinations, and the second step is to restore the 20 billion combinations.

If we compare the restoration of the Rubik's Cube to letting a boat sail to a fixed destination in the vast ocean, then the 20 billion color combinations proposed by Coshenba are like a special water area - a special water area 20 billion times larger than that fixed place. The two steps he proposed are like letting the boat sail to that special water area first, and then sail from there to the fixed destination. It is obviously much easier to find a huge special water area in the vast ocean than to directly find the small destination. This is the advantage of Coshenba's new idea. But even so, it is still not easy to estimate the "God's number" using Coshenba's method. In particular, in order to perform fast calculations, it is best to store the minimum number of rotations to restore the 20 billion color combinations (which is equivalent to the map of the "special water area") in the computer's memory, which requires about 300 megabytes of memory. 300 megabytes seems not a large number today, but in the year when Coshenba proposed the new idea, the memory of ordinary machines was far less than one-tenth of it. Therefore, it was not until three years later that someone used Kosenba's method to give the first estimate. This person was an American mathematician named M. Reid.

In 1995, Reed found through calculation that any color combination of the Rubik's Cube can be turned into one of Cosenba's 20 billion combinations after at most 12 turns, and any one of the 20 billion combinations can be restored after at most 18 turns. This shows that any color combination of the Rubik's Cube can be restored after at most 12+18=30 turns. Using this idea, in 2007, it was proved that the "God's number" cannot be greater than 26. In other words, only 26 turns are needed to ensure that the Rubik's Cube with any color combination can be restored. But this number is not the "God's number" because Cosenba's new idea has an obvious limitation, that is, it must first go through one of the special color combinations he selected. In fact, some restoration methods with the least number of turns do not go through those special color combinations. Therefore, although Cosenba's new idea reduces the amount of calculation, the restoration method found is not necessarily the one with the least number of turns.

Image source: pexls

In order to break through this limitation, mathematicians have adopted a compromise, which is to appropriately increase the number of special color combinations, because the larger the number, the greater the possibility that the restoration method with the least number of rotations will pass through those special color combinations. Of course, doing so will undoubtedly increase the amount of calculation. However, the rapid development of computer technology soon offset the increase in the amount of calculation.

In 2008, computer expert Tom Rokicki used this compromise to reduce the estimated value of "God's number" to 22. In other words, only 22 turns are needed to ensure that any color combination of the Rubik's Cube can be restored. So, is the number 22 the "God's number"? The answer is no. An obvious sign of this is that people have never found any color combination that requires more than 20 turns to restore. This makes people guess that "God's number" should be 20 (it cannot be less than 20, because many color combinations have been proven to require 20 turns to restore).

In July 2010, this conjecture was finally proved by Kosenba himself and several collaborators. Therefore, we can now answer the question "How many turns are needed to restore the Rubik's Cube?" with the certainty that is unique to mathematics. The answer is: 20.

This article is reproduced from / Origin Reading

Editor/Xiao Xitushuo