Pushing blocks is hard. (Q1395573)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Pushing blocks is hard. |
scientific article |
Statements
Pushing blocks is hard. (English)
0 references
1 July 2003
0 references
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.
0 references
computational complexity
0 references
computational geometry
0 references
motion planning
0 references
combinatorial games
0 references
NP-hard
0 references
push-X open problem
0 references
robot
0 references
Eulerian tours of planar graphs
0 references
