Tetris is NP-hard even with O(1) rows or columns (2020) [pdf]
11 comments
·September 1, 2025westurner
"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
NoahZuniga
But not with both O(1) rows and columns!
rthnbgrredf
I haven't thought that the game is actually that hard. However, Hateris actually is https://github.com/qntm/hatetris
Keyframe
Haha, thank you for this. I will implement this in my personal version of tetris!
relwin
Why is the paper's copyright footer "1992 Information Processing Society of Japan" when this work is actually from around 2019?
ansgri
Probably used an outdated LaTeX template.
JohnKemeny
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).
dang
Good catch! Based on https://arxiv.org/abs/2009.14336, I put 2020 in the title above.
Interesting! Not really that surprising, since another dimension (rows/columns/piece size) is O(n). But pretty cool.