Paper by Erik D. Demaine
- Erik D. Demaine and Michael Hoffmann, “Pushing Blocks is NP-Complete for Noncrossing Solution Paths”, in Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001), Waterloo, Ontario, Canada, August 13–15, 2001, pages 65–68.
We prove NP-hardness of a wide class of pushing-block puzzles like
the classic Sokoban, generalizing several previous results
[4, 5, 7, 8, 13, 15].
The puzzles consist of unit square blocks on an integer lattice; all
blocks are movable. The robot may move horizontally and vertically
in order to reach a specified goal position. In the Push-k
puzzle, the robot can push up to k blocks in front of it as long
as there is at least one free square ahead.
Other variations were introduced to make puzzles more tractable, in
which blocks must slide their maximal extent when pushed
(Push-Push), and in which the robot's path must not cross itself
X). We prove that all of these puzzles are NP-hard.
- This paper is also available from the electronic proceedings as http://compgeo.math.uwaterloo.ca/~cccg01/proceedings/long/eddemaine-24711.ps.gz.
- The paper is 5 pages.
- The paper is available in PostScript (326k) and gzipped PostScript (90k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- PushingBlocks_CGTA (Pushing Blocks is Hard)
- Related webpages:
- Pushing Blocks
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 13, 2019 by