And it keeps on turning

Around 500 million Rubik’s Cubes have been sold worldwide to date. This makes it the most successful puzzle game ever. It is estimated that one in seven people has held one in their hands. “But I didn’t want to create a toy,” Ernő Rubik told ETH News in Zurich last week. The Department of Mathematics invited Rubik to ETH Zurich, as his 80^th birthday this year coincides with the Cube’s 50th anniversary.

In 1974, as a 30-year-old architecture lecturer in Budapest, he was working on a geometric problem and how it could be represented – perhaps as a three-dimensional, cube-shaped object that could rotate around its axis. In his autobiography, Rubik writes that he finally found answers to his questions: “Or rather, the answers found me in a 3x3x3 object with red, white, orange, green, blue and yellow faces. And that was that.”

When Rubik made a few turns on his first, colourfully painted wooden model 50 years ago, he was fascinated by how everything changed. But he soon realised that he was no longer able to return to the starting point and make each of the six sides of the cube the same colour again: “I was locked in an escape room that I had designed myself, and the rules weren’t written on the wall. How foolish of me!” It took him a whole month to restore the cube to its original state. Later, he made it in a minute.

The world record set a year ago is an incredible 3.13 seconds, and speedcubing has become a popular sport with strictly regulated competitions all over the world. Just how popular it is was demonstrated at a conference organised by the ETH Department of Mathematics in honour of Rubik, which was attended by professors, researchers and students as well as primary school pupils. A boy asked the inventor how he felt when players could solve his cube in three seconds. When the boy, asked by the moderator, said he could solve it in 13 seconds, he received a round of applause.

Patent for a logical toy

No matter how you turn the cube, you always have a limited view of it. “The challenge is that you have to see all sides to know if you can solve the problem,” explains Rubik. The cube therefore promotes spatial imagination and served Rubik as a teaching aid in his architecture lessons. When his friends became interested in his invention, he realised that the cube was more than a tool to illustrate spatial motion; it also had commercial potential. In 1975, he patented it as a “three-dimensional, logical toy”. In 1977, the Cube was sold for the first time in Hungarian toy shops. Subsequently, companies in the UK and the US took over international distribution.

Rubik describes himself as “a man who likes to play – a Homo ludens”. Even as a small child, he searched for puzzles and spent hours immersing himself in them: “One of my favourite pursuits was developing strategies for new and more efficient solutions.” He stresses that solving puzzles is more than just entertainment or a pastime: “Puzzles reveal important qualities in each of us: concentration, curiosity, the joy of playing, the eagerness to find a solution. These are the same qualities that form the basis of all human creativity.”

Quintillions of possibilities

As a challenging puzzle, the cube is also ideal for learning algebra and computer algebra, scientists explained at the aforementioned conference at ETH. “When I was young and got my hands on the cube for the first time, I was immediately fascinated,” explains Martin Kreuzer, Professor of Mathematics at the University of Passau. “Maths is less about learning and more about the ability to solve problems, and the cube is a particularly attractive problem.”

It’s a problem that group theory can help solve. If you consider the cube as a mathematical model, you get a group of motions that can be applied to its respective states. Each sequence of rotations of the cube corresponds to an element in the group, and each state of the cube can be described by the position and orientation of the individual “cubies” or “cubelets”. With the help of group theory, we can calculate how many possible states there are: over 43 quintillion – a huge number with 20 digits.

By repeatedly applying a specific sequence of four rotations, it is possible to restore any cube configuration to its initial state. This sequence is called a commutator in technical jargon. “While solving the cube this way is rather slow, it gives insight into the structure of the group,” explains Kreuzer.

Searching for God’s Number

But how can the cube puzzle be solved as quickly as possible? Or to put it another way: how many turns at most would an omniscient being need to restore any configuration of the cube to its original state? The search for what is known as God’s number lasted for decades. It was not until 2010, thanks to improved processing power and sophisticated algorithms, that a research team was able to analyse all possible positions of the cube – over 43 quintillion. They discovered that God’s number is astonishingly small: it is 20.

In order to find an algorithm that solves the Rubik’s Cube with the smallest possible number of turns, the possible configurations can be represented as a huge network whose nodes are connected to each other if two configurations can be converted into one another by one turn. “In computer science, we call these networks graphs,” explained Václav Rozhoň, a computer scientist at the ETH Department of Computer Science and the Bulgarian AI institute INSAIT, which was jointly founded with ETH and EPFL. It can also be used to visualise road networks or friendships on social networks.

Meeting in the middle

Using graph theory, Rozhoň and his colleagues succeeded in developing a computer algorithm that returns any configuration of the Rubik’s Cube to its original state in as few steps as possible. The trick is to start the calculations simultaneously at two locations: the origin, and another arbitrary position. When they finally meet at the halfway point, the shortest solution will have been reached, hence the name of this process: “meet in the middle”. “The exciting thing about the Rubik’s Cube is how many concepts you can explore if you just try to gain a little more insight into how it works,” says Rozhoň.