Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433789 | Theoretical Computer Science | 2016 | 12 Pages |
Abstract
We prove PSPACE-completeness of a broad class of moving-blocks problems similar to the well-known puzzle Sokoban. Several computational complexity results are known for moving-blocks problems. However, most of the literature is focused on problems with push moves and the complexity of many of them are still open. In this article, we study the computational complexity of moving-blocks problems with pull moves and problems with push and pull moves. Our reductions are from Nondeterministic Constraint Logic. We improve the known NP-hardness results of Pull problems to PSPACE-completeness results. We also were able to show that the whole class of PushPull problems is PSPACE-complete.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
André G. Pereira, Marcus Ritt, Luciana S. Buriol,