7 papers · 1 filter
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
MIT Hardness Group, Josh Brunner, Lily Chung +4
We prove that Hamiltonicity in maximum-degree-3 grid graphs (directed or undirected) is ASP-complete, i.e., it has a parsimonious reduction from every NP search problem (including…
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…
Complexity of 2D Snake Cube Puzzles
MIT Hardness Group, Nithid Anchaleenukoon, Alex Dang +3
Given a chain of cubes where each cube is marked "turn " or "go straight", when can it fold into a rectangular box? We prove several variants o…
You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
MIT Hardness Group, Hayashi Ani, Lilly Hall +5
We prove RE-completeness (and thus undecidability) of several 2D games in the Super Mario Bros. platform video game series: the New Super Mario Bros. series (original, Wii, U, and…
Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
MIT Hardness Group, Della Hendrickson, Andy Tockman
We study three problems related to the computational complexity of the popular game Minesweeper. The first is consistency: given a set of clues, is there any arrangement of mines t…
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…