Tetris is Hard with Just One Piece Type
2026-03-10 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study how hard it is for a computer to solve certain Tetris problems when only one type of piece is used. They prove that for almost all Tetris pieces, figuring out if you can clear the board or survive without losing is NP-hard, meaning it's computationally difficult. This result even disproves a long-standing belief about the I-piece version of Tetris under a common rotation system. On the other hand, they provide fast algorithms for simpler cases like domino pieces and some specific conditions with rectangular pieces. Their work clarifies when these Tetris problems are hard and when they can be solved efficiently.
TetrisNP-hardnesspolyominotetrominoSuper Rotation System (SRS)computational complexitypolynomial-time algorithmI-piecedomino7-bag randomizer
Authors
MIT Hardness Group, Josh Brunner, Erik D. Demaine, Della Hendrickson, Jeffery Li
Abstract
We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining whether the player can avoid losing before placing all the given pieces in an initial board) when restricted to a single polyomino piece type. We prove, for any tetromino piece type $P$ except for O, the NP-hardness of Tetris clearing and survival under the standard Super Rotation System (SRS), even when the input sequence consists of only a specified number of $P$ pieces. These surprising results disprove a 23-year-old conjecture on the computational complexity of Tetris with only I pieces (although our result is only for a specific rotation system). As a corollary, we prove the NP-hardness of Tetris clearing when the sequence of pieces has to be able to be generated from a $7k$-bag randomizer for any positive integer $k\geq 1$. On the positive side, we give polynomial-time algorithms for Tetris clearing and survival when the input sequence consists of only dominoes, assuming a particular rotation model, solving a version of a 9-year-old open problem. Along the way, we give polynomial-time algorithms for Tetris clearing and survival with $1\times k$ pieces (for any fixed $k$), provided the top $k-1$ rows are initially empty, showing that our I NP-hardness result needs to have filled cells in the top three rows.