 Tetris

A single player game in which the player packs tetrominoes in a rectangular grid. Description

Tetris is an interactive single player game played on a rectangular grid. Initially some of the cells of the grid are filled and some are empty. The gameplay is as follows: a tetromino piece is generated at the top of the board and starts falling towards the last row. The player can rotate the piece and slide it horizontally. The fall stops when the piece reaches the last row or lands on an occupied square of the board. The player has a final chance to slide or rotate the piece before it is locked into place and a new tetromino is generated from the top. Whenever a generic $i$-th row of the grid is entirely filled by cells corresponding locked pieces it is cleared, i.e., each row $1 \lt j \le i$ is replaced by row $j-1$ and row $1$ is replaced by an empty row.

The game terminates when a new tetromino can no longer be generated at the top of the board, as at least one of the corresponding cells is filled.

Computational complexity

The following results have been obtained  on the version of the game in which the player knows in advance a finite sequence of $p$ tetrominoes that will be generated:

• Maximizing the number of rows cleared is NP-hard is not approximable within a factor $p^{1-\epsilon}$, for any constant $\epsilon > 0$.

• Maximizing the number of tetrominoes placed is not approximable within a factor $p^{1-\epsilon}$, for any constant $\epsilon > 0$.

• Maximizing the number of tetrises, i.e., the simultaneous clearing of four rows is NP-hard.

• Minimizing the height of the highest filled grid cell is not approximable within a factor $2-\epsilon$, for any constant $\epsilon > 0$.

 E. D. Demaine, S. Hohenberger, D. Liben-Nowell, “Tetris is Hard, Even to Approximate”, in COCOON 2003.