Tetris is NP-hard even with O(1) rows or columns [pdf]
29 isaacfrond 5 9/1/2025, 12:49:57 PM martindemaine.org ↗
Comments (5)
rthnbgrredf · 23s ago
I haven't thought that the game is actually that hard. However, Hateris actually is https://github.com/qntm/hatetris
relwin · 24m ago
Why is the paper's copyright footer "1992 Information Processing Society of Japan" when this work is actually from around 2019?
ansgri · 20m ago
Probably used an outdated LaTeX template.
pretzellogician · 1h ago
Interesting! Not really that surprising, since another dimension (rows/columns/piece size) is O(n). But pretty cool.
dooglius · 26m ago
Needs (1992)