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...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Information Processing Society of Japan
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143958 |
| _version_ | 1811095532891799552 |
|---|---|
| author | Asif, Sualeh Coulombe, Michael Demaine, Erik D Demaine, Martin L Hesterberg, Adam Lynch, Jayson Singhal, Mihir |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Asif, Sualeh Coulombe, Michael Demaine, Erik D Demaine, Martin L Hesterberg, Adam Lynch, Jayson Singhal, Mihir |
| author_sort | Asif, Sualeh |
| collection | MIT |
| description | © 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 to the previous reduction for unrestricted board sizes, but with a better packing of buckets. On the positive side, we prove that 2-column Tetris (and 1-row Tetris) is polynomial. We also prove that the generalization of Tetris to larger k-omino pieces is NP-complete even when the board starts empty, and even when restricted to 3 columns or 2 rows or constant-size pieces. Finally, we present an animated Tetris font. |
| first_indexed | 2024-09-23T16:18:59Z |
| format | Article |
| id | mit-1721.1/143958 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:18:59Z |
| publishDate | 2022 |
| publisher | Information Processing Society of Japan |
| record_format | dspace |
| spelling | mit-1721.1/1439582023-06-28T18:16:21Z Tetris is NP-hard even with O (1) Rows or Columns Asif, Sualeh Coulombe, Michael Demaine, Erik D Demaine, Martin L Hesterberg, Adam Lynch, Jayson Singhal, Mihir Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 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 to the previous reduction for unrestricted board sizes, but with a better packing of buckets. On the positive side, we prove that 2-column Tetris (and 1-row Tetris) is polynomial. We also prove that the generalization of Tetris to larger k-omino pieces is NP-complete even when the board starts empty, and even when restricted to 3 columns or 2 rows or constant-size pieces. Finally, we present an animated Tetris font. 2022-07-22T14:17:19Z 2022-07-22T14:17:19Z 2020 2022-07-22T14:14:30Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/143958 Asif, Sualeh, Coulombe, Michael, Demaine, Erik D, Demaine, Martin L, Hesterberg, Adam et al. 2020. "Tetris is NP-hard even with O (1) Rows or Columns." Journal of Information Processing, 28 (0). en 10.2197/IPSJJIP.28.942 Journal of Information Processing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Information Processing Society of Japan MIT web domain |
| spellingShingle | Asif, Sualeh Coulombe, Michael Demaine, Erik D Demaine, Martin L Hesterberg, Adam Lynch, Jayson Singhal, Mihir Tetris is NP-hard even with O (1) Rows or Columns |
| title | Tetris is NP-hard even with O (1) Rows or Columns |
| title_full | Tetris is NP-hard even with O (1) Rows or Columns |
| title_fullStr | Tetris is NP-hard even with O (1) Rows or Columns |
| title_full_unstemmed | Tetris is NP-hard even with O (1) Rows or Columns |
| title_short | Tetris is NP-hard even with O (1) Rows or Columns |
| title_sort | tetris is np hard even with o 1 rows or columns |
| url | https://hdl.handle.net/1721.1/143958 |
| work_keys_str_mv | AT asifsualeh tetrisisnphardevenwitho1rowsorcolumns AT coulombemichael tetrisisnphardevenwitho1rowsorcolumns AT demaineerikd tetrisisnphardevenwitho1rowsorcolumns AT demainemartinl tetrisisnphardevenwitho1rowsorcolumns AT hesterbergadam tetrisisnphardevenwitho1rowsorcolumns AT lynchjayson tetrisisnphardevenwitho1rowsorcolumns AT singhalmihir tetrisisnphardevenwitho1rowsorcolumns |