Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Ani, Joshua; Chung, Lily; Demaine, Erik D.; Diomidov, Yevhenii; Hendrickson, Dylan; Lynch, Jayson https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-159737
URL:

; ; ; ; ;

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

pdf-format:


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.

BibTeX - Entry

@InProceedings{ani_et_al:LIPIcs.FUN.2022.3,
  author =	{Ani, Joshua and Chung, Lily and Demaine, Erik D. and Diomidov, Yevhenii and Hendrickson, Dylan and Lynch, Jayson},
  title =	{{Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{3:1--3:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15973},
  URN =		{urn:nbn:de:0030-drops-159737},
  doi =		{10.4230/LIPIcs.FUN.2022.3},
  annote =	{Keywords: gadgets, motion planning, hardness of games}
}

Keywords: gadgets, motion planning, hardness of games
Seminar: 11th International Conference on Fun with Algorithms (FUN 2022)
Issue date: 2022
Date of publication: 23.05.2022


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI