TL;DR
This paper proves that the classic game of Tetris remains NP-complete even when the playfield is restricted to a mere 8 columns or 4 rows. This settles long-standing open questions about the computational complexity of Tetris, demonstrating its inherent difficulty even in highly constrained forms.
What Problem Does This Paper Address?
The game of Tetris, despite its simple appearance, has been known to be NP-hard for some time. However, a key open question was whether this NP-hardness persisted when the game's dimensions were significantly reduced. Specifically, researchers wondered if Tetris would become computationally easier if the playfield had a very small, constant number of columns or rows. This paper tackles this question by investigating the complexity of Tetris under these strict dimensional constraints.
Methods
The authors employ a reduction-based approach, a common technique in computational complexity theory. They reduce known NP-hard problems to specific Tetris variants to demonstrate that these Tetris variants are also NP-hard.
- 3-PARTITION Reduction: The primary method used is a reduction from the strongly NP-hard 3-PARTITION problem. This involves constructing a Tetris game instance such that a solution to the 3-PARTITION problem corresponds directly to a winning strategy (surviving or clearing the board) in the Tetris game.
- Novel Piece Sequences and Board Configurations: To achieve the NP-completeness results for restricted dimensions, the authors devise intricate initial board configurations and carefully crafted sequences of Tetris pieces. These constructions are designed to precisely mimic the constraints and requirements of the 3-PARTITION problem.
- Case Analysis and Proof by Contradiction: Many of the proofs involve detailed casework and arguments by contradiction. The authors meticulously analyze all possible ways pieces can be placed and show that any deviation from a specific strategy leads to an unsolvable state, thus forcing a solution that mirrors the 3-PARTITION solution.
- Polynomial-Time Algorithms: For simpler cases (e.g., 2-column Tetris), the authors provide polynomial-time algorithms, establishing the precise thresholds for NP-completeness.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Tetris's Enduring Hardness: The most striking insight is that Tetris's computational complexity doesn't significantly diminish even with drastically reduced board sizes. This suggests that the core difficulty lies not just in the sheer scale of the problem but in the combinatorial nature of piece fitting and line clearing.
- The Power of "Buckets" and "Corridors": The reduction techniques heavily rely on constructing specific board features, like "buckets" and "corridors," which act as sophisticated mechanisms to encode the constraints of the 3-PARTITION problem. The precise shape and arrangement of these features are crucial for the reduction to work.
- Critical Thresholds: The paper pinpoints critical thresholds for the number of columns and rows that determine NP-completeness. For instance, Tetris with 2 columns is polynomial, but with 8 columns it becomes NP-complete, highlighting a significant jump in complexity within a small range.
- Empty Board Complexity: A notable contribution is proving NP-hardness for Tetris starting from an empty board, a problem that was previously a major open question. This is achieved by forcing the player to construct a specific initial configuration using Tetris pieces.
Key Results
- NP-completeness for Restricted Columns: Tetris is proven to be NP-complete for $c$-column Tetris where $c \ge 8$. This includes the common 8-column width of some Tetris variants.
- NP-completeness for Restricted Rows: Tetris is proven to be NP-complete for $r$-row Tetris where $r \ge 4$.
- Polynomial Solvability: Tetris with 2 columns ($c=2$) is shown to be solvable in polynomial time. Tetris with 1 row ($r=1$) is also polynomial.
- Empty Board NP-hardness: Tetris starting from an empty board is NP-hard for $c \ge 8$ columns and $k$-omino pieces, and for 3 columns with $O(n)$ pieces. It is also NP-hard for 2 rows with $O(n)$ pieces.
- Tetris Font: The paper introduces a Tetris font where each letter is constructed from tetrominoes, demonstrating a creative application of Tetris piece manipulation.
Limitations and Future Work
- Open Thresholds: The exact minimum number of columns ($c^*$) and rows ($r^*$) for which Tetris becomes NP-complete remain open questions. The paper establishes $c^* \in [3, 8]$ and $r^* \in [2, 4]$, but the precise values are unknown.
- Partial Lock-Out Rule: The hardness proof for $c$-column Tetris survival relies on the "partial lock-out" rule (where a piece extending above the top row causes a loss). The paper notes that modern Tetris versions have a different rule, and it's an open question whether Tetris survival remains NP-hard without the partial lock-out rule.
- Holding Function: The impact of a "holding" function (allowing players to store a piece for later use) on Tetris's complexity is an open area for future research.
- Imperfect Information/Randomness: The complexity of Tetris with imperfect information or randomness is also left as an open problem.
Summary updated