**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*, to appear. 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. **Length**:- The paper is 13 pages.
**Availability**:- 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.

Last updated July 25, 2017 by Erik Demaine.