Paper by Erik D. Demaine
- 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, to appear. Special issue of papers from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games
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.
- The paper is 13 pages.
- The paper is available in PDF (602k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Tetris_IJCGA (Tetris is Hard, Even to Approximate)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 25, 2017 by