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:
Currently unavailable. If you are in a rush for copies, contact me.
[Google Scholar search]


See also other papers by Martin Demaine.
These pages are generated automagically from a BibTeX file.
Last updated November 20, 2018 by Martin Demaine.