Tetris with Few Piece Types

MIT Hardness Group, Erik D. Demaine, Holden Hall +1

We prove NP-hardness and #P-hardness of Tetris clearing (clearing an initial board using a given sequence of pieces) with the Super Rotation System (SRS), even when the pieces are…