Paper by Erik D. Demaine
- Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch, “Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude”, in Proceedings of the 11th International Conference on Fun with Algorithms (FUN 2022), Island of Favignana, Sicily, Italy, May 30–June 3, 2022, 2:1–2:30.
We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F,
a theoretical abstraction of many video games (first posed in 1999). We also
prove PSPACE-completeness of two versions of the recently studied block-moving
puzzle game with gravity, Block Dude — a video game dating back to 1994
— featuring either liftable blocks or pushable blocks. Two of our
reductions are built on a new framework for “checkable” gadgets,
extending the motion-planning-through-gadgets framework to support gadgets
that can be misused, provided those misuses can be detected later.
- The paper is available in PDF (1387k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 19, 2022 by