Mihir Singhal

Tetris is NP-hard even with <i>O</i>(1) Rows or Columns

2020 · Journal of Information Processing

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 problems posed over 15 years ago. Our …