Paper by Erik D. Demaine

Reference:

Hayashi Ani, Lily Chung, Erik D. Demaine, Jenny Diomidova, Della 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.

BibTeX

@InProceedings{GadgetsChecked_FUN2022,
  AUTHOR        = {Hayashi Ani and Lily Chung and Erik D. Demaine and Jenny Diomidova and Della Hendrickson and Jayson Lynch},
  authororig    = {Joshua Ani and Lily Chung and Erik D. Demaine and Yevhenii Diomidov and Dylan Hendrickson and Jayson Lynch},
  TITLE         = {Pushing Blocks via Checkable Gadgets: {PSPACE}-completeness of {Push-1F} and {Block/Box Dude}},
  BOOKTITLE     = {Proceedings of the 11th International Conference on Fun with Algorithms (FUN 2022)},
  bookurl       = {https://sites.google.com/view/fun2022/home},
  ADDRESS       = {Favignana, Italy},
  MONTH         = {May 30--June 3},
  YEAR          = 2022,
  PAGES         = {2:1--2:30},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.FUN.2022.3},
  dblp          = {https://dblp.org/rec/conf/fun/AniCDDHL22},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.4230/LIPIcs.FUN.2022.3">LIPIcs</A>.},
}

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.

Comments:

This paper is also available from LIPIcs.

Availability:

The paper is available in PDF (1387k).

See information on file formats.

[Google Scholar search]