×

Tetris is hard, even to approximate. (English) Zbl 1093.90045

Summary: In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled squares; any completely filled row of the gameboard is cleared and all filled squares above it drop by one row. We prove that in the offline version of Tetris, it is \(\mathbf {NP}\)-complete to maximize the number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously filled and cleared), minimize the maximum height of an occupied square, or maximize the number of pieces placed before the game ends. We furthermore show the extreme inapproximability of the first and last of these objectives to within a factor of \(p^{1-\varepsilon}\), when given a sequence of \(p\) pieces, and the inapproximability of the third objective to within a factor of \(2-\varepsilon\), for any \(\varepsilon>0\). Our results hold under several variations on the rules of Tetris, including different models of rotation, limitations on player agility, and restricted piece sets.

MSC:

90C27 Combinatorial optimization
05A99 Enumerative combinatorics
90C60 Abstract computational complexity for mathematical programming problems
91A99 Game theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Sheff D., Game Over: Nintendo’s Battle to Dominate an Industry (1993)
[2] Kim S., Games Mag. pp 66–
[3] Burgiel H., Mathematical Gazette pp 194–
[4] DOI: 10.1007/BF03025367 · Zbl 1052.68624 · doi:10.1007/BF03025367
[5] Garey M. R., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) · Zbl 0411.68039
[6] DOI: 10.1137/0204035 · Zbl 0365.90076 · doi:10.1137/0204035
[7] DOI: 10.1016/0022-0000(85)90045-5 · Zbl 0583.68020 · doi:10.1016/0022-0000(85)90045-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.