Paper by Martin L. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Adam Hesterberg, Andrea Lincoln, Jayson Lynch, and Y. William Yu, “Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes, …”, Journal of Information Processing, volume 25, 2017, pages 515–527. Special issue of papers from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games

Abstract:

We consider variations on the classic video game Tetris where pieces are k-ominoes instead of the usual tetrominoes (k = 4), as popularized by the video games ntris and Pentris. We prove that it is NP-complete to survive or clear a given initial board with a given sequence of pieces for each k ≥ 5, complementing the previous NP-completeness result for k = 4. More surprisingly, we show that board clearing is NP-complete for k = 3; and if pieces may not be rotated, then clearing is NP-complete for k = 2 and survival is NP-complete for k = 3. All of these problems can be solved in polynomial time for k = 1.

Comments:

This paper is also available from J-STAGE.

Length:

The paper is 13 pages.

Availability:

The paper is available in PDF (602k).

See information on file formats.

[Google Scholar search]

Related webpages:

Tetris Font