Paper by Erik D. Demaine

Reference:

Sualeh Asif, Michael Coulombe, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jayson Lynch, and Mihir Singhal, “Tetris is NP-hard even with O(1) rows or columns”, Journal of Information Processing, volume 28, 2020, pages 942–958.

BibTeX

@Article{ThinTetris_JIP,
  AUTHOR        = {Sualeh Asif and Michael Coulombe and Erik D. Demaine and Martin L. Demaine and Adam Hesterberg and Jayson Lynch and Mihir Singhal},
  TITLE         = {Tetris is {NP}-hard even with {$O(1)$} rows or columns},
  JOURNAL       = {Journal of Information Processing},
  journalurl    = {http://www.ipsj.or.jp/english/jip/},
  VOLUME        = 28,
  YEAR          = 2020,
  PAGES         = {942--958},

  withstudent   = 1,
  length        = {19 pages},
  replaces      = {ThinTetris_JCDCGGG2019},
  papers        = {ThinTetris_JCDCGGG2019},
  doi           = {https://dx.doi.org/10.2197/ipsjjip.28.942},
  dblp          = {https://dblp.org/rec/journals/jip/AsifCDDHLS20},
  comments      = {This paper is available as <A HREF="https://arXiv.org/abs/2009.14336">arXiv:2009.14336</A> and from <A HREF="https://doi.org/10.2197/ipsjjip.28.942">J-STAGE</A>.},
  webpages      = {fonts/tetris},
}

Abstract:

We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open problems posed over 15 years ago [2]. Our reduction is from 3-Partition, similar to the previous reduction for unrestricted board sizes, but with a better packing of buckets. On the positive side, we prove that 2-column Tetris (and 1-row Tetris) is polynomial. We also prove that the generalization of Tetris to larger k-omino pieces is NP-complete even when the board starts empty, and even when restricted to 3 columns or 2 rows or constant-size pieces. Finally, we present an animated Tetris font.

Comments:

This paper is available as arXiv:2009.14336 and from J-STAGE.

Length:

The paper is 19 pages.

Availability:

The paper is available in PDF (1403k).

See information on file formats.

[Google Scholar search]

Related papers:

ThinTetris_JCDCGGG2019 (Tetris is NP-hard even with O(1) Columns)

Related webpages:

Tetris Font