Scientists have proved that the minimum reduction step of the Rubik's Cube is 20.

Although there are 43,252,003,274,489,856,000 different possible combination states, the Rubik's Cube can be restored in 20 steps.

Beijing time on August 13, according to foreign media reports, I believe many people have played the Rubik's Cube, but no one knows what the minimum reduction steps of any combination of Rubik's Cube are. This problem has puzzled mathematicians for more than 30 years, and this minimum step size is also called "magic number". Scientists in California recently solved the mystery with computers. Researchers have proved that any combination of the Rubik's Cube can be restored in 20 steps, and the "number of gods" is officially set at 20.

This research team is located in Palo Alto, California, USA. Scientists have calculated and proved by computer that any combination of Rubik's Cube can be restored in 20 steps. This result shows that about 65438+ ten thousand initial states can be restored in only 20 steps.

Using the powerful computing power of Google computer, the researchers examined any possible chaotic state of the Rubik's Cube (the exact number is 43252007489856000). Professor Morey Davidson, a mathematician at Kent State University in Ohio, USA, is also one of the researchers. He said, "We can now determine that the number of gods is 20. For me, I went back to the past. Rubik's cube grew up with me, which is why I studied this math problem deeply. This mystery has aroused widespread concern, and it may be the most popular riddle in human history. " The scientists' preliminary research results were published on the online website, but Davidson said that they intend to submit their research results to the magazine for official publication.

Programmer Thomas Rocchi spent 15 years trying to find the answer to this mystery. According to Rocchi, the algorithm adopted by the research team can try 1 100 million possibilities in 1 second, while the previous computer algorithm can only handle 4,000 possibilities in 1 second.

To simplify the problem, the research team adopted a mathematical technique called "group theory". They first divided all possible initial state sets of the Rubik's Cube into 2.2 billion sets, and each set contained 65.438+0.95 billion possible states. The allocation principle of sets is how these possible states respond to a set of 10 possible recovery steps. Through the different symmetry of the Rubik's Cube, this grouping technology enables the research team to reduce the number of collections to 56 million.

The algorithm adopted by the researchers can quickly match these reduction steps to the appropriate starting point, thus handling 65.438+095 billion possibilities in a set within 20 seconds. For an ordinary home computer, it takes about 35 years to complete the whole processing task at this speed.

In 2007, the Daily Telegraph reported that any combination of Rubik's Cube can be restored in 26 steps. Of course, there are other reports that prove that there are fewer steps to reduce. The Rubik's Cube was invented by Hungarian professor Elnor rubik in 1974. It used to be the best-selling intellectual toy in the world.