26 citations · 54 across the 9 of their papers we have counts for
4 papers · 1 filter
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…
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…
The Complexity of Clickomania
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine +3
We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player…
Phutball Endgames are Hard
Erik D. Demaine, Martin L. Demaine, David Eppstein
We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game.…