Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Tetris is Hard with Just One Piece Type
MIT Hardness Group, Josh Brunner, Erik D. Demaine +2
We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining wh…
cs.CC2026
Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
MIT Hardness Group, Zachary Abel, Erik D. Demaine +3
Given a graph, when can we orient the edges to satisfy local constraints at the vertices, where each vertex specifies which local orientations of its incident edges are allowed? Th…
cs.CC2024
Tetris with Few Piece Types
MIT Hardness Group, Erik D. Demaine, Holden Hall +1
We prove NP-hardness and #P-hardness of Tetris clearing (clearing an initial board using a given sequence of pieces) with the Super Rotation System (SRS), even when the pieces are…