Complexity of Tetris

Alexey_Pajitnov_-_2575833305_(crop)
Alexey Pajitnov, Russian video game developer and computer engineer who created Tetris

In the 1980s, while testing hardware, Alexey Pajitnov, takes and old childhood game and streamlines it. By combining the Greek word “Tetra” with his favorite sport, Tennis, Tetris is born. Today, Tetris is one of the most popular games in history, with countless variants and copies played worldwide with many interesting computational problems.

For anyone who has played Tetris,the game progressively gets harder. The blocks move faster, and the amount of losses accumulate, which poses an interesting question, just how hard is Tetris? In computing, Tetris is considered to be NP-complete for the following version and goals: Given a Tetris game where all the pieces are known in advance what are:

  1. The maximum number of rows that can be cleared
  2. The maximum number of piece that can be cleared before a loss
  3. The maximum number of simultaneous four row clears
  4. The minimum highest height that is reached per game

NP problems are all problems whose solutions can be quickly checked for accuracy. Of these problems the ones that can be easily solved are called P problems while the ones that are difficult to solve are called NP-complete problems. These four are proved to be NP-complete by showing that an NP-complete problem, 3-Partitian Problem, could be quickly computed if there was a way to quickly compute any of those four Tetris problems.

Complexity_classes

Interestingly enough, the iconic Tetris theme song, Korobeiniki, is a russian folk song about a traveling salesman. In computing the Traveling Salesman Problem is considered to be NP-hard meaning that it is much harder than the Tetris Problems.

Sources Used