Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude

Authors Joshua Ani, Lily Chung , Erik D. Demaine , Yevhenii Diomidov, Dylan Hendrickson , Jayson Lynch



PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.3.pdf
  • Filesize: 1.53 MB
  • 30 pages

Document Identifiers

Author Details

Joshua Ani
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Lily Chung
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Erik D. Demaine
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Yevhenii Diomidov
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Dylan Hendrickson
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Jayson Lynch
  • Cheriton School of Computer Science, University of Waterloo, Canada

Acknowledgements

This work was initiated during extended problem solving sessions with the participants of the MIT class on Algorithmic Lower Bounds: Fun with Hardness Proofs (6.892) taught by Erik Demaine in Spring 2019. We thank the other participants for their insights and contributions. We would like to thank our reviewers for their detailed and useful feedback. We would like to thank Aaron Williams for useful discussion including how to restructure the paper and how to better present the results and checkable gadget framework. Figures produced using SVG Tiler (https://github.com/edemaine/svgtiler), diagrams.net, and Inkscape.

Cite AsGet BibTex

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 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 3:1-3:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.3

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • gadgets
  • motion planning
  • hardness of games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A, 461:3473-3482, 2005. URL: https://doi.org/http://doi.org/10.1098/rspa.2005.1546.
  2. Joshua Ani, Sualeh Asif, Erik D Demaine, Yevhenii Diomidov, Dylan Hendrickson, Jayson Lynch, Sarah Scheffler, and Adam Suhl. PSPACE-completeness of pulling blocks to reach a goal. Journal of Information Processing, 28:929-941, 2020. Google Scholar
  3. Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch. Walking through doors is hard, even without staircases: Proving PSPACE-hardness via planar assemblies of door gadgets. In Proceedings of the 10th International Conference on Fun with Algorithms (FUN 2020), Favignana, Italy, September 2020. Google Scholar
  4. Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, and Jayson Lynch. Traversability, reconfiguration, and reachability in the gadget framework. In Petra Mutzel, Md. Saidur Rahman, and Slamin, editors, Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), volume 13174 of Lecture Notes in Computer Science, pages 47-58, Jember, Indonesia, March 2022. URL: https://doi.org/10.1007/978-3-030-96731-4_5.
  5. Austin Barr, Calvin Chang, and Aaron Williams. Block dude puzzles are NP-hard (and the rugs really tie the reductions together). In Proceedings of the 33rd Canadian Conference on Computational Geometry, Halifax, Canada, 2021. Google Scholar
  6. Joseph Culberson. Sokoban is PSPACE-complete. In Proceedings of the International Conference on Fun with Algorithms, pages 65-76, Elba, Italy, June 1998. Google Scholar
  7. Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, and Joseph O'Rourke. Pushing blocks is hard. Computational Geometry: Theory and Applications, 26(1):21-36, August 2003. Google Scholar
  8. Erik D. Demaine, Martin L. Demaine, and Joseph O'Rourke. PushPush and Push-1 are NP-hard in 2D. In Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG 2000), pages 211-219, Fredericton, Canada, August 2000. Google Scholar
  9. Erik D. Demaine, Isaac Grosof, Jayson Lynch, and Mikhail Rudoy. Computational complexity of motion planning of a robot through simple gadgets. In Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), pages 18:1-18:21, La Maddalena, Italy, June 2018. Google Scholar
  10. Erik D. Demaine, Robert A. Hearn, and Michael Hoffmann. Push-2-F is PSPACE-complete. In Proceedings of the 14th Canadian Conference on Computational Geometry, pages 31-35, Lethbridge, Canada, August 2002. Google Scholar
  11. Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch. Toward a general theory of motion planning complexity: Characterizing which gadgets make games hard. In Proceedings of the 11th Conference on Innovations in Theoretical Computer Science, Seattle, Washington, January 2020. arXiv:1812.03592. Google Scholar
  12. Dylan Hendrickson. Gadgets and gizmos: A formal model of simulation in the gadget framework for motion planning. Master’s thesis, Massachusetts Institute of Technology, 2021. Google Scholar
  13. Jayson Lynch. A framework for proving the computational intractability of motion planning problems. PhD thesis, Massachusetts Institute of Technology, 2020. Google Scholar
  14. Joseph O'Rourke and The Smith Problem Solving Group. PushPush is NP-hard in 3D. arXiv:cs/9911013, November 1999. URL: https://arXiv.org/abs/cs/9911013.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail