Push-Pull Block Puzzles are Hard

DOI10.1007/978-3-319-57586-5_16zbMath1487.68243arXiv1709.01241OpenAlexW2963425277MaRDI QIDQ5283366

Jayson Lynch, Erik D. Demaine, Isaac Grosof

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

zbMATH Keywords

complexitypuzzlesmotion planningPSPACE-completenessNP

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ The Parameterized Complexity of Motion Planning for Snake-Like Robots

Cites Work

• Unnamed Item
• Unnamed Item
• Motion planning in the presence of movable obstacles
• SOKOBAN and other motion planning problems
• Classic Nintendo games are (computationally) hard
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants

This page was built for publication: Push-Pull Block Puzzles are Hard