In July 2008, many of the best Rubik's Cube players from all over the world gathered in Pardubice in the center of the Czech Republic to participate in the most important Rubik's Cube world. Event: Czech Open. In this competition, Dutch player E. Akkersdijk set an astonishing record: it only took 7.08 seconds to restore a Rubik's Cube whose colors were completely disrupted. Coincidentally, in August of this year, people also made important progress in studying the mathematical problems behind the Rubik's Cube. In this article, we will introduce the Rubik's Cube and the mathematical problems behind it.
1. Toys that are popular around the world
In the spring of 1974, E. Rubik, a professor of architecture at the Budapest College of Applied Arts in Hungary, came up with the idea of As an interesting idea, he wanted to design a teaching tool to help students intuitively understand the various rotations of space geometry. After thinking, he decided to make a 3×3×3 cube composed of some small squares, with each side capable of rotating at will. Such a cube can easily demonstrate various spatial rotations.
Although this idea is good, it faces a thorny problem in practice, that is, how to make all sides of such a cube rotate at will? Rubik came up with many ideas, such as using magnets or rubber bands to connect the small squares, but he was unsuccessful. One afternoon that summer, while he was enjoying the cool air by the Danube River, his eyes inadvertently fell on the pebbles by the river. Suddenly, a new idea flashed through his mind: using a round surface similar to the surface of pebbles to process the internal structure of the cube. This new idea was successful, and Rubik quickly completed his design and applied for a patent with the Hungarian Patent Office. This design is the magic cube that we are all familiar with, also called Rubik's cube [Note 1].
Six years later, led by a Hungarian businessman and amateur mathematician, Rubik’s Cube entered the Western European and American markets, and became a trendy toy that swept the world at an alarming rate. Over the next 25 years, more than 300 million Rubik's Cubes were sold. Among the Rubik's Cube players, there are children learning to speak and CEOs of multinational companies. Although the Rubik's Cube did not become a teaching tool for spatial geometry as Rubik envisioned, it became the best-selling toy of all time.
The best-selling magic of the Rubik's Cube lies in its astonishing number of color combinations. When a Rubik's Cube leaves the factory, each face has a color, and there are six colors in total. However, after these colors are disrupted, the number of combinations that can be formed is as many as 432.5 trillion [Note 2]. If we made each of these combinations into a Rubik's cube, these Rubik's cubes could be lined up from the earth to the distant stars 250 light-years away. In other words, if we light a light at one end of such a row of Rubik's Cubes, it will take 250 years for the light to reach the other end. If any diligent player wants to try all the combinations, even if he does not eat, drink or sleep, and spins out ten different combinations every second, it will take 150 billion years to do so (for comparison, we The universe is currently less than 14 billion years old). Compared with such combinations, adjectives such as "thousands," "hundreds of millions," and "billions" commonly used by advertisers to bluff and deceive customers have become rare humility. . We can say with confidence that if one turns around at will without mastering the know-how, even if a person starts playing Rubik's Cube from the beginning of the Big Bang, there is almost no hope of restoring a Rubik's Cube whose colors have been disrupted.
2. Rubik’s Cube and “God’s Number”
With more Rubik’s Cube players, competitions between them are naturally inevitable. Since 1981, Rubik's Cube enthusiasts have begun to hold world-wide Rubik's Cube competitions and thus began to set their own world records. This record is constantly being refreshed, and as of the time of writing this article, the fastest record for restoring the Rubik's Cube - as we mentioned at the beginning of this article - has reached an astonishing 7.08 seconds. Of course, there is a certain degree of contingency in the record of a single restoration. In order to reduce this contingency, since 2003, the winner of the Rubik's Cube Competition has been determined by the average score of multiple restorations [Note 3]. This average score is currently the world record. is 11.28 seconds. The emergence of these records shows that although the Rubik's Cube has astronomical color combinations, as long as you master the trick, the number of turns required to restore any combination is not many.
So, how many rotations are needed to ensure that no matter what color combination is restored [Note 4]? This problem has aroused the interest of many people, especially mathematicians. The minimum number of turns required to restore any combination is nicknamed "God's number" by mathematicians, and the Rubik's Cube, the darling of the toy world, has invaded the academic world because of this "God's number".
To study "God's Number", of course, we must first study the method of restoring the Rubik's Cube. In the process of playing Rubik's Cube, people have long known that it is easy to restore any given color combination, which has been demonstrated by countless outstanding records of players. However, the recovery method used by Rubik's Cube players is a method that is easy for the human brain to grasp, but it is not the one with the least number of turns, so it is not helpful in finding the "God's Number". Finding the method with the fewest number of turns is a difficult mathematical problem. Of course, this problem is not difficult for mathematicians. As early as the mid-1990s, people had relatively practical algorithms that could find the minimum number of turns to restore a given color combination in an average of about fifteen minutes. Theoretically, if one could find such a minimum number of spins for every color combination, then the largest of these spins would undoubtedly be the "God's number." But unfortunately, the huge number of 432.5 trillion has become an obstacle for people to peek into the "number of God". If the algorithm mentioned above is used, even if 100 million machines are used to calculate it at the same time, it will take more than 10 million years to complete.
It seemed that recklessness would not work, so mathematicians turned to their old profession: mathematics. From a mathematical point of view, although the color combinations of the Rubik's Cube are ever-changing, they are actually produced by a series of basic operations (i.e. rotations), and those operations also have several very simple characteristics. For example, every operation has an opposite. Operation (for example, the opposite operation to clockwise rotation is counterclockwise rotation). For such operations, mathematicians have a very effective tool in their arsenal to deal with it. This tool is called group theory, which appeared more than 140 years before the advent of the Rubik's Cube. It is said that the German mathematics master D. Hilbert once said that the trick to learning group theory is to choose a good example. Since the advent of the Rubik's Cube, mathematicians have written several books about group theory through the Rubik's Cube. Therefore, although the Rubik's Cube has not become a teaching tool for space geometry, it can be used as a "good example" for learning group theory to a certain extent.
For the study of Rubik's Cube, group theory has a very important advantage, that is, it can make full use of the symmetry of the Rubik's Cube. When we mentioned the huge number 4325 billion earlier, there was actually an omission, that is, we did not take into account the symmetry of the Rubik's Cube as a cube.
The result is that many of the 432.5 billion color combinations are actually exactly the same, just viewed from different angles (for example, with different sides facing up). Therefore, the daunting figure of 432.5 billion is actually "pork injected with water." So, what proportion of "moisture" is in this "pork"? When I said it, everyone was shocked: it accounted for nearly 99%! In other words, based on symmetry alone, mathematicians can reduce the color combinations of the Rubik's Cube by two orders of magnitude [Note 5].
But reducing it by two orders of magnitude is not enough to find the "God's number", because it is just reducing the aforementioned ten million years to one hundred thousand years. One hundred thousand years is obviously too long to solve a mathematical problem, and we don't expect anyone to actually use 100 million computers to calculate the "number of God." Although mathematicians are wise, they are not necessarily rich in other aspects. The only thing they can really use is the machine on their desk. Therefore, in order to find the “number of God”, people still need to find more clever ideas. Fortunately, the power of group theory as a tool goes far beyond analyzing obvious things like the symmetry of a cube, and with its help new ideas quickly emerged.
3. Searching for the "God's Number"
In 1992, the German mathematician H. Kociemba proposed a new idea for finding a method to restore the Rubik's Cube. He discovered that among the basic rotation methods of the Rubik's Cube, some parts can form a series of their own, and nearly 20 billion color combinations can be formed through this part of rotation [Note 6]. Using these 20 billion combinations, Cosenba decomposed the Rubik's Cube recovery problem into two steps: the first step is to transform any color combination into one of the 20 billion combinations; the second step is to transform the 200 Billions of combinations are restored. If we compare solving the Rubik's Cube to a boat in the vast ocean sailing to a fixed destination, then the 20 billion color combinations proposed by Cosenba are like a special area of ??water - a area larger than that fixed location. special waters that are 20 billion times larger. The two steps he proposed were like having the boat first sail to that particular piece of water, and then sail from there to that fixed destination. It is obviously much easier to find a huge special water area in the vast ocean than to directly find that small destination. This is the advantage of Cosenba's new idea.
But even so, it is not easy to estimate the "number of God" using Cosenba's method. In particular, for fast calculations, it is best to store the minimum number of turns to restore the 20 billion color combinations (which is equivalent to the map of the "special water") in the computer's memory, which requires about 300 megabytes. of memory. 300 megabytes seems like a small number today, but in the year when Cosenba proposed the new idea, the memory of ordinary machines was far less than one-tenth of that. Therefore, it was not until three years later that someone used Cosenba's method to provide the first estimation results. This person's name is M. Reid, a mathematician at the University of Central Florida. In 1995, Reed found through calculations that after a maximum of 12 turns, any color combination of the Rubik's Cube can be turned into one of Cosambana's 20 billion combinations; and after a maximum of 18 turns, the 200 color combinations can be changed. Restore any one of billions of combinations. This shows that after a maximum of 12 18 = 30 turns, any color combination of the Rubik's Cube can be restored.
After obtaining the above results, Reed quickly improved his calculations and reduced the result from 30 to 29, which showed that the "number of God" would not exceed 29.
Since then, with the development of computer technology, mathematicians have made further improvements to Reed's results, but the progress has not been rapid. It was not until 11 years later in 2006 that Silviu Radu, a doctoral student at the Research Institute for Symbolic Computation at Johannes Kepler University in Austria, advanced the result to 27. The next year, in 2007, computer scientists D. Kunkle and G. Cooperman of Northeastern University in the United States advanced the result to 26. Their work used a parallel computing system. The memory used is as high as 7 million terabytes, and the computing time consumed is as long as 8,000 hours (equivalent to nearly a year of 24-hour non-stop computing).
These calculations show that the “number of God” cannot exceed 26. However, the greatest advantage of all these calculations - namely, the use of Cosenba's "special water" - is also their most fatal weakness, because the recovery methods they give must pass through that special water. But in fact, the best way to restore many color combinations is not to go through that special water area at all. For example, any small boat that is close to the destination but happens not to be in the special water area obviously does not need to be deliberately like the direct charter flights from mainland China and Taiwan. Take a detour from that special body of water before heading to your destination. Therefore, the restoration method obtained by using Cosenba's ideas may not be the best, and the estimate of the "number of God" made from this is also very likely to be an overestimation.
However, what should we do if we do not introduce the special waters of Cosenba and the amount of calculation is too large? Mathematicians decided to adopt a compromise method, that is, to expand the "area" of the special water area, because the larger the special water area, the greater the possibility that the best recovery path happens to pass through it (of course, the amount of calculation will also have a corresponding Increase). In 2008, T. Rokicki, a computer expert who has been studying the "number of God" for 15 years, used an ingenious method equivalent to expanding Cosenba's special waters thousands of times, and in just a few Four consecutive violent attacks were launched on the "Number of God" within a month, compressing its estimated value from 25 to 22. As of this writing, this is the best result worldwide. Rokic's calculations are supported by Sony Pictures Imageworks, the film special effects maker that has created special effects for famous films such as "Spider-Man" and provided Rokic with 50 years' worth of non-stop computing power. required computer resources.
So, now we know that the “number of God” must not exceed 22. However, although the special water area of ????Rokic is large, there are still many color combinations that are best restored without passing through that special water area. Therefore, the "God's number" is likely to be smaller than 22. So, how much is it? Although people still don't know for sure, there are various indications that it is very likely to be 20. That's because, in all of their efforts over the years—including the roughly four quadrillion color combinations that Rokich directly calculated—we've never encountered any color combination that required more than 20 turns to recover. , which indicates that the "number of God" is probably not greater than 20. On the other hand, tens of thousands of color combinations have been discovered that require 20 turns to restore, indicating that the "God's number" cannot be less than 20. Putting these two aspects together, mathematicians generally believe that the true value of "God's number" is 20.
Of course, "God" may be subtle, and none of us can guarantee whether it will surprise us somewhere. The only thing we have reason to believe may be: the mysterious "God of God" intertwined with mathematics. "The day when it comes to light is not too far away."
Notes
1. Rubik’s Cube is the name given by Rubik himself to this cube, while Rubik’s Cube is the name given by the American toy company Ideal Toys. In Western countries, the name Rubik's Cube is more popular, while in China, the name Rubik's Cube is more popular. In addition, readers should be reminded that there are many types of Rubik's Cubes, and the 3×3×3 Rubik's Cube introduced in this article is only the most common one.
2. The specific calculation is as follows: Among the small cubes that make up the Rubik's Cube, there are 8 vertices, and there are 8! kinds of substitutions between them; each of these vertices has 3 colors, and in the direction There are 37 combinations of upwards (due to structural limitations, only 7 vertices of the Rubik's Cube can have independent directions). Similarly, the Rubik's Cube has 12 small cubes as sides, and there are 12!/2 kinds of permutations between them (the reason why it is divided by 2 is because once the vertices of the Rubik's Cube are determined, only half of the permutations of the edges are possible); these edges Each has two colors, and there are 211 combinations in orientation (due to structural limitations, only 11 sides of the Rubik's Cube can have independent orientations). Therefore, the total number of color combinations in the Rubik's Cube is 8! × 37 × 12! It is also worth mentioning that if we allow the Rubik's Cube to be dismantled and reassembled, the structural limitations mentioned above will no longer exist, and the number of color combinations will be as many as 51.9 trillion. However, the increase in the number of combinations does not mean that the difficulty of recovery becomes greater. The restriction of the number of combinations by the Rubik's Cube structure is actually the main reason that makes the recovery of the Rubik's Cube difficult. For example, there are about 40 billion combinations of the twenty-six English letters by exchanging adjacent letters, which is far more than the number of combinations of Rubik's Cube colors. However, by exchanging adjacent letters, It is very simple to restore the randomly arranged twenty-six English letters to their original arrangement from A to Z.
3. To be exact, take the average of the three median scores out of five attempts.
4. In order to make this question meaningful, of course we must first define what rotation is. In the mathematical study of the Rubik's Cube, rotation refers to rotating any face of the Rubik's Cube (containing 9 small squares) by 90° or 180° in the clockwise or counterclockwise direction. For each face, such a rotation* **There are 3 types (readers, please think about it, why not 4 types?). Since the Rubik's Cube has 6 faces, there are 18 basic ways of turning it.
5. To be precise, 10 of the 18 basic rotation modes form a series of their own, and the resulting color combinations are 8!×8!×4!/2 (approximately 195 billion) species.