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

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 (18)

• 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
• Threes!, Fives, 1024!, and 2048 are hard
• 2048 without new tiles is still hard
• On the complexity of Two Dots for narrow boards and few colors
• 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
• An algorithmic analysis of the Honey-Bee game
• Online square packing with gravity
• Bust-a-Move/Puzzle Bobble is NP-complete
• On the complexity of jelly-no-puzzle
• Combinatorial analysis of tetris-like games
• Two Dots is NP-complete
• Tetris and decidability
• Morpion solitaire

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)