TETRIS IS HARD, EVEN TO APPROXIMATE

DOI10.1142/S0218195904001354zbMATH Open1093.90045OpenAlexW2146302034MaRDI QIDQ4818596FDOQ4818596

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

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

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

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)

Cites Work

• Title not available (Why is that?)
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Minesweeper is NP-complete.
• Games against nature

Cited In (13)

• Bust-a-Move/Puzzle Bobble Is NP-complete
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle
• How fast can we play Tetris greedily with rectangular pieces?
• Threes!, Fives, 1024!, and 2048 are hard
• Online Square Packing
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
• Assembling molecules in ATOMIX is hard
• Tetris is Hard, Even to Approximate
• On the Complexity of Two Dots for Narrow Boards and Few Colors.
• An algorithmic analysis of the Honey-Bee game
• Online square packing with gravity
• On the complexity of jelly-no-puzzle
• Combinatorial analysis of tetris-like games

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)