Tetris is NP-hard even with $O(1)$ rows or columns

Sualeh Asif, Michael Coulombe, Erik D. Demaine +4

We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open prob…