6 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…
Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
Hayashi Ani, Lily Chung, Erik D. Demaine +3
We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (introduced in 1999). The proof also extends to Push-$k…
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…
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…
PSPACE-Hard 2D Super Mario Games: Thirteen Doors
MIT Hardness Group, Hayashi Ani, Erik D. Demaine +4
We prove PSPACE-hardness for fifteen games in the Super Mario Bros. 2D platforming video game series. Previously, only the original Super Mario Bros. was known to be PSPACE-hard (F…