Paper by Erik D. Demaine

Reference:

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), Favignana, Italy, May 30–June 3, 2022, 2:1–2:30.

Abstract:

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.

Availability:

The paper is available in PDF (1387k).

See information on file formats.

[Google Scholar search]