English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove that the classic falling-block video game Tetris (both survival andboard clearing) remains NP-complete even when restricted to 8 columns, or to 4rows, settling open problems posed over 15 years ago [BDH+04]. Our reduction isfrom 3-Partition, similar to the previous reduction for unrestricted boardsizes, but with a better packing of buckets. On the positive side, we provethat 2-column Tetris (and 1-row Tetris) is polynomial. We also prove that thegeneralization of Tetris to larger $k$-omino pieces is NP-complete even whenthe board starts empty, even when restricted to 3 columns or 2 rows orconstant-size pieces. Finally, we present an animated Tetris font.

Tetris is NP-hard even with $O(1)$ rows or columns