TETRIS IS HARD, EVEN TO APPROXIMATE

DOI10.1142/S0218195904001354zbMATH Open1093.90045OpenAlexW2146302034MaRDI QIDQ4818596FDOQ4818596

Authors Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, David Liben-Nowell, Walter A. Kosters

Publication date 29 September 2004

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195904001354

zbMATH Keywords

computational complexityalgorithmic combinatorial game theoryTetris

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60) Game theory (91A99)

Recommendations

• Tetris is Hard, Even to Approximate
• Tetris and decidability
• 2048 without new tiles is still hard
• Tetris player: Strategy driven algorithm
• From Tetris to polyominoes generation
• Tetris: A study of randomized constraint sampling
• Threes!, Fives, 1024!, and 2048 are hard

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Games against nature
• Minesweeper is NP-complete.

Cited in

(18)

• Two Dots is NP-complete
• How fast can we play Tetris greedily with rectangular pieces?
• Tetris and decidability
• Bust-a-Move/Puzzle Bobble is NP-complete
• Morpion solitaire
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
• Tetris is Hard, Even to Approximate
• 2048 without new tiles is still hard
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle
• Threes!, Fives, 1024!, and 2048 are hard
• Online Square Packing
• Combinatorial analysis of tetris-like games
• Threes!, Fives, 1024!, and 2048 are hard
• An algorithmic analysis of the Honey-Bee game
• Assembling molecules in ATOMIX is hard
• On the complexity of Two Dots for narrow boards and few colors
• On the complexity of jelly-no-puzzle
• Online square packing with gravity

This page was built for publication: TETRIS IS HARD, EVEN TO APPROXIMATE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4818596)