Paper by Erik D. Demaine
- 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.
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 .
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.
- This paper is available as arXiv:2009.14336 and from J-STAGE.
- The paper is 19 pages.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 21, 2021 by