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…