Paper by Erik D. Demaine

Reference:

Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, and David Liben-Nowell, “Tetris is Hard, Even to Approximate”, International Journal of Computational Geometry and Applications, volume 14, number 1–2, 2004, pages 41–68.

BibTeX

@Article{Tetris_IJCGA,
  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},
  journalurl    = {http://www.worldscinet.com/ijcga/ijcga.shtml},
  VOLUME        = 14,
  NUMBER        = {1--2},
  YEAR          = 2004,
  PAGES         = {41--68},

  length        = {28 pages},
  papers        = {Tetris_COCOON2003; Tetris_CGW2002; Tetris_TR2002; TotalTetris_JIP},
  doi           = {https://dx.doi.org/10.1142/S0218195904001354},
  dblp          = {https://dblp.org/rec/journals/ijcga/BreukelaarDHHKL04},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1142/S0218195904001354">WorldSciNet</A> and as <A HREF="https://arXiv.org/abs/cs/0210020">arXiv:cs/0210020</A>.},
  updates       = {Ivars Peterson wrote an article describing these results,
                   &ldquo;<A HREF="http://www.sciencenews.org/20021026/mathtrek.asp">Tetris
                   Is Hard</A>&rdquo;,
                   <I><A HREF="http://www.sciencenews.org/">Science
                   News</A></I> 162(17), October 26, 2002.
                   <P>
                   Helen Pearson also wrote an article describing these results,
                   &ldquo;<A HREF="http://www.nature.com/nsu/021021/021021-9.html">Maths
                   proves Tetris is tough</A>&rdquo;,
                   <I><A HREF="http://www.nature.com/nsu/">Nature
                   Science Update</A></I>, October 28, 2002.
                   <P>
                   Sarah Graham also wrote a short article describing these
                   results,
                   &ldquo;<A HREF="http://www.sciam.com/article.cfm?chanID=sa003&articleID=000EB124-AE08-1DBD-94E2809EC5880108">Mathematicians
                   Prove Tetris is Tough</A>&rdquo;,
                   <I><A HREF="http://www.sciam.com/news_directory.cfm">Scientific
                   American News</A></I>, October 29, 2002.},
  replaces      = {Tetris_COCOON2003; Tetris_CGW2002},
  withstudent   = 1,
  webpages      = {fonts/tetris},
}

Abstract:

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 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.

Comments:

This paper is also available from WorldSciNet and as arXiv:cs/0210020.

Updates:

Ivars Peterson wrote an article describing these results, “Tetris Is Hard”, Science News 162(17), October 26, 2002.

Helen Pearson also wrote an article describing these results, “Maths proves Tetris is tough”, Nature Science Update, October 28, 2002.

Sarah Graham also wrote a short article describing these results, “Mathematicians Prove Tetris is Tough”, Scientific American News, October 29, 2002.

Length:

The paper is 28 pages.

Availability:

The paper is available in PostScript (3283k), gzipped PostScript (330k), and PDF (355k).

See information on file formats.

[Google Scholar search]

Related papers:

Tetris_COCOON2003 (Tetris is Hard, Even to Approximate)

Tetris_CGW2002 (Tetris is Hard, Even to Approximate)

Tetris_TR2002 (Tetris is Hard, Even to Approximate)

TotalTetris_JIP (Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes, …)

Related webpages:

Tetris Font