26 citations · 66 across the 12 of their papers we have counts for
Showing 2002 · cs.CCShow all
2 papers · 2 filters
cs.CC2002
Tetris is Hard, Even to Approximate
Erik D. Demaine, Susan Hohenberger, David Liben-Nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configurati…
cs.CC2002★ 3 cited
PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation
Robert A. Hearn, Erik D. Demaine
We present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether thi…