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

Interesting! Not really that surprising, since another dimension (rows/columns/piece size) is O(n). But pretty cool.

But not with both O(1) rows and columns!

I haven't thought that the game is actually that hard. However, Hateris actually is https://github.com/qntm/hatetris

Why is the paper's copyright footer "1992 Information Processing Society of Japan" when this work is actually from around 2019?

Needs (1992)

"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