Tetris is NP-hard even with O (1) Rows or Columns

Tetris is NP-hard even with O (1) Rows or Columns

© 2020 Information Processing Society of Japan. 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 reduction is from 3-Partition, similar...

Full description

Bibliographic Details
Main Authors: Asif, Sualeh, Coulombe, Michael, Demaine, Erik D, Demaine, Martin L, Hesterberg, Adam, Lynch, Jayson, Singhal, Mihir
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:English
Published: Information Processing Society of Japan 2022
Online Access:https://hdl.handle.net/1721.1/143958

Internet

https://hdl.handle.net/1721.1/143958

Similar Items