Push-pull block puzzles are hard

DOI10.1007/978-3-319-57586-5_16MaRDI QIDQ5283366zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Isaac Grosof, Jayson Lynch

Publication date 21 July 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.01241, https://hdl.handle.net/1721.1/121270

zbMATH Keywords

complexitymotion planningPSPACE-completenesspuzzlesNP

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Artificial intelligence for robotics (68T40)

Abstract: This paper proves that push-pull block puzzles in 3D are PSPACE-complete to solve, and push-pull block puzzles in 2D with thin walls are NP-hard to solve, settling an open question by Zubaran and Ritt. Push-pull block puzzles are a type of recreational motion planning problem, similar to Sokoban, that involve moving a `robot' on a square grid with $1imes1$ obstacles. The obstacles cannot be traversed by the robot, but some can be pushed and pulled by the robot into adjacent squares. Thin walls prevent movement between two adjacent squares. This work follows in a long line of algorithms and complexity work on similar problems. The 2D push-pull block puzzle shows up in the video games Pukoban as well as The Legend of Zelda: A Link to the Past, giving another proof of hardness for the latter. This variant of block-pushing puzzles is of particular interest because of its connections to reversibility, since any action (e.g., push or pull) can be inverted by another valid action (e.g., pull or push).

Recommendations

• Pushing blocks is hard.
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• scientific article; zbMATH DE number 2002586
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• PSPACE-completeness of Bloxorz and of games with 2-buttons

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 2048 without new tiles is still hard
• Classic Nintendo games are (computationally) hard
• Motion planning in the presence of movable obstacles
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Relationships between nondeterministic and deterministic tape complexities
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
• SOKOBAN and other motion planning problems

Cited in

(7)

• PSPACE-completeness of Bloxorz and of games with 2-buttons
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
• Computational complexity of motion planning of a robot through simple gadgets
• Pushing blocks is hard.
• scientific article; zbMATH DE number 7779759 (Why is no real title available?)
• The parameterized complexity of motion planning for snake-like robots
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete

This page was built for publication: Push-pull block puzzles are hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283366)