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

combinatorial gamescomputational complexitycomputational geometryEulerian tours of planar graphsmotion planningNP-hardpush-X open problemrobot

Mathematics Subject Classification ID

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

Review text

The authors study several variations of simpler puzzles and show that the models are NP-hard. The results subsume a number of previous NP-hardness proofs of pushing-block variations, and solve the Push-X open problem. The main idea in the is to force the robot to follow constrained Eulerian tours of planar graphs and carry a constant amount of information along each edge of the graph. Moreover it is build a kind of logic engine. This approach is innovative and contrast with other previous approaches of building circuits based on graphs.

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

(17)

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