2026-09-30T09:24:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25751 2026-09-23T23:49:32Z ddc:004 open_access

Tetris Is Hard with Just One Piece Type MIT Hardness Group Brunner, Josh Demaine, Erik D. Hendrickson, Della Li, Jeffery complexity hardness video games counting 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 ≥ 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 × 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik MIT Hardness Group and Josh Brunner and Erik D. Demaine and Della Hendrickson and Jeffery Li 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.32 urn:nbn:de:0030-drops-257515 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.32 eng https://creativecommons.org/licenses/by/4.0/legalcode