Pushing blocks is hard.

DOI10.1016/S0925-7721(02)00170-0MaRDI QIDQ1395573zbMATH OpenOpenAlexFDO

Authors D. Massart

Publication date 1 July 2003

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0925-7721(02)00170-0

zbMATH Keywords

computational complexitycomputational geometrycombinatorial gamesmotion planningNP-hardrobotEulerian tours of planar graphspush-X open problem

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Kinematics of mechanisms and robots (70B15) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Games involving graphs (91A43)

Recommendations

• Push-pull block puzzles are hard
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• SOKOBAN and other motion planning problems
• \(1\times 1\) Rush Hour with fixed blocks is PSPACE-complete

Cites work

• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1262793 (Why is no real title available?)
• scientific article; zbMATH DE number 1182933 (Why is no real title available?)
• Motion planning in the presence of movable obstacles
• Parallel concepts in graph theory
• SOKOBAN and other motion planning problems

Cited in

(16)

• scientific article; zbMATH DE number 3883607 (Why is no real title available?)
• Push-pull block puzzles are hard
• The computational complexity of Angry Birds
• Computational complexity of motion planning of a robot through simple gadgets
• Randolphs Robot Game is NP-hard!
• Hybrid planning for challenging construction problems: an answer set programming approach
• Automated Technology for Verification and Analysis
• scientific article; zbMATH DE number 7779759 (Why is no real title available?)
• Difficulty rating of Sokoban puzzle
• HIROIMONO Is NP-Complete
• CADbots: algorithmic aspects of manipulating programmable matter with finite automata
• Ice sliding games
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• The snowblower problem
• Forming tile shapes with simple robots
• The \((n^ 2-1)\)-puzzle and related relocation problems

This page was built for publication: Pushing blocks is hard.

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