## Tetris is Hard, Even to Approximate [ps |
ps.gz |
pdf ]

In *
International Journal of Computational Geometry and Applications*,
14(1-2):41-68, April 2004.

A previous version of parts of this paper appears in *Proceedings
of COCOON
2003* by Erik D. Demaine, Susan Hohenberger, and David
Liben-Nowell.

A two-page version (ps, pdf) appears in *Proceedings of Fall Workshop on
Computational Geometry '02* by the same authors.

The most recent update to this document was on 04 August 2005.

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 pieces above
it drop by one row. We prove that in the offline version of Tetris,
it is 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-ε)*, when
given a sequence of p pieces, and the inapproximability of the third
objective to within a factor of *(2 - ε)*, for any
*ε>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.

@Article{bdhhkln:tetris-ijcga2004,
author = {Ron Breukelaar
and Erik D.~Demaine
and Susan Hohenberger
and Hendrik Jan Hoogeboom
and Walter A.~Kosters
and David Liben-Nowell},
title = {Tetris is Hard, Even to Approximate},
journal = {International Journal of Computational Geometry
and Applications},
year = 2004,
volume = 14,
number = {1--2},
pages = {41--68},
month = apr,
}

*David Liben-Nowell*

*04 August 2005*