Tetris is NP-hard even with O(1) rows or columns (2020) [pdf]

66 isaacfrond 14 9/1/2025, 12:49:57 PM martindemaine.org ↗

Comments (14)

pretzellogician · 5h ago
Interesting! Not really that surprising, since another dimension (rows/columns/piece size) is O(n). But pretty cool.
NoahZuniga · 4h ago
But not with both O(1) rows and columns!
tomsmeding · 1h ago
Well, if there are no n dimensions the problem doesn't scale and there is no complexity to be had, because it's finite. :)
NoahZuniga · 47m ago
Exactly!
rthnbgrredf · 4h ago
I haven't thought that the game is actually that hard. However, Hateris actually is https://github.com/qntm/hatetris
Keyframe · 3h ago
Haha, thank you for this. I will implement this in my personal version of tetris!
nurettin · 37m ago
Tetris is already kind of like that. My version avoids dropping the same piece consecutively (re-roll once on duplicate) in order to get a more realistic Tetris experience.
relwin · 5h ago
Why is the paper's copyright footer "1992 Information Processing Society of Japan" when this work is actually from around 2019?
dang · 4h ago
Good catch! Based on https://arxiv.org/abs/2009.14336, I put 2020 in the title above.
ansgri · 4h ago
Probably used an outdated LaTeX template.
JohnKemeny · 4h ago
Not so much outdated as simply not filled in. This is a submitted pdf, not proofed pdf. You can see that both volume and page numbers are missing.

These are things filled in by the journal in the proofing stage (after peer review).

dooglius · 5h ago
Needs (1992)
indeed30 · 4h ago
I think it's actually (2020)
westurner · 3h ago
"From Nand to Tetris (2017)" https://news.ycombinator.com/item?id=38735066 .. From https://www.nand2tetris.org/ :

> Nand to Tetris courses are taught at 400+ universities, high schools, and bootcamps. The students who take them range from high schoolers to Ph.D. students to senior engineers. Here is an extended syllabus of a typical academic-version course.

There's now a schema.org/Syllabus Class .

> Similar: "Show HN: Tetris, but the blocks are ARM instructions that execute in the browser" https://news.ycombinator.com/item?id=37086102

What is the computational complexity of Tetris with ARM instructions?

In ASM;

Rosetta Code > Tetris: https://rosettacode.org/wiki/Tetris :

> tetromino.py - Python implementation of Tetris included with Raspbian