The Impossible Problems Hidden in a Simple Game of Tetris
How complex can a simple game be? Tetris pushes even supercomputers to their limits and amazes mathematicians
The gameplay screen of the game Tetris as seen on a 1989 Nintendo Game Boy.
Russell Hart/Alamy Stock Photo
See the world through the lens of science. Sign up for our free, daily newsletter Today in Science.
As a child of the 1990s, I couldn’t avoid the game-turned-best-seller Tetris. Launched in 1984 by Russian programmer Alexey Pajitnov, Tetris quickly became a blockbuster and has had hundreds of millions of players over the years. I myself spent hours on my Game Boy trying to position falling bricks so that they would fill the playing field as completely as possible. Over the course of a game, those blocks fell faster and faster, and my thumbs could barely keep up with the controls.
In principle, all games—even those as varied as Candy Crush Saga, Magic: The Gathering and Wordle—can be examined from a mathematical perspective. But Tetris has many special connections to mathematics. For instance, the game’s goal strongly resembles geometry’s parquet problems, in which you determine whether you can cover an area with an infinitely large set of tiles without any gaps.
But Tetris is especially intriguing to mathematicians in terms of its complexity. More specifically, researchers have wondered about the computing power that it takes to determine how or if someone can truly “solve” Tetris, assuming conditions such as a finite number of bricks and the ability to know the order in which various shapes will appear. It turns out that that particular framing places Tetris among the most mathematically complex games.
On supporting science journalism
If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Defining Complexity
In the field of complexity theory, mathematicians and computer scientists seek to characterize the difficulty involved in solving problems. They have defined multiple complexity classes, or categories, including P and NP problems. Simply put, P problems are easy for conventional computers to solve, whereas NP problems are more difficult but, in the event you have a possible solution, easy to check. (NP problems can be thought of like a Sudoku puzzle: it may take hours to fill in the fields, but it only takes a few minutes to see whether the solution is correct.)
To determine the complexity of a task, one must compare different problems with each other. If every algorithm that solves task A can also solve task B, for example, then A is more complex than B. Or as mathematicians put it: B is “reducible” to A. That means that by comparing Tetris with another known P or NP problem, its complexity can be determined.
So how do we pick a good point of comparison? Computer scientists can turn to so-called NP-complete problems, to which all other NP problems can be reduced. One of these is the three-partition problem.
Tetris on a Nintendo Gameboy at the Computer Games Museum Berlin.
IMAGO/Eibner-Pressefoto/Jonas Lohrmann/Alamy Stock Photo
The three-partition problem deals with the question of whether a given set of integers, for example {1, 2, 5, 6, 7, 9}, can be divided into subsets with three elements each such that the sum of the numbers in the subsets is always equal. For {1, 2, 5, 6, 7, 9}, a division would be {1, 5, 9} and {2, 6, 7}. The contents of each subset add up to 15. Such a division is not possible for every given set. Finding out whether this exists or not proves to be extremely difficult: the three-partition problem is NP-complete.
In 2003 computer scientists at the Massachusetts Institute of Technology demonstrated that the question of whether a Tetris board can be cleared in a given game situation can itself be mapped to the three-partition problem. To do this, the researchers equated the gaps in the Tetris game with the subsets of the problem and the falling bricks with the numbers that have to be split up.
In this way, the scientists showed that if the set of numbers can be divided into three-element subsets with the same sum, then the Tetris playing field can also be completely emptied. In doing so, they proved that the questions “Can a set be divided into a three-partition?” and “Can the Tetris playing field be emptied?” are identical from a mathematical point of view.
This insight means the puzzle of whether given bricks can be arranged appropriately falls into the category of NP-complete problems, making Tetris a highly complex game. The longer the sequence of bricks that the game contains, the more time-consuming it is for a computer to determine the solvability. And indeed, conventional computers will be overwhelmed very quickly: there is no algorithm that can solve the problem efficiently.
Tetris Reaches the Limits of Computability
Tetris has even more complex properties, as computer scientists Hendrik Jan Hoogeboom and Walter Kosters, both at Leiden University in the Netherlands, showed in a 2004 paper. They looked at a slightly different question. Let’s assume that you observe a game of Tetris that only features the elongated, I-shaped brick. If I gave you a predetermined number of ways for, say, 40 I-shaped tiles to fall onto an empty Tetris board, could you decide whether, among those eight ways, there is one for which the board ends up empty?
Hoogeboom and Kosters proved that this question is, in fact, undecidable, even with an infinite amount of computing power. That’s because the aforementioned question can be mapped to a problem that relates to Kurt Gödel’s infamous incompleteness theorems. These state that there will always be statements in mathematics that can neither be proved nor disproved.
Of course, these questions likely have no effect on your success at Tetris. With the speed at which pieces fall, there is hardly any time to think about mathematical problems.
Still, it’s remarkable that after more than 40 years, Tetris appreciation continues to grow and evolve, even as the game remains essentially unchanged. For instance, a playing technique known as “rolling” (which allows very fast inputs to be made) has made it possible to advance further than ever before. In the past, the 29th level was seen as an insurmountable limit. But in 2023 a then 13-year-old broke all previous records by rolling through to level 157, causing the game to crash. We can only wait and see what surprises Tetris has in store in the future.
This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.