Paper by Erik D. Demaine
- Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, and Joseph O'Rourke, “Pushing Blocks is Hard”, Computational Geometry: Theory and Applications, volume 26, number 1, August 2003, pages 21–36. Special issue of selected papers from the 13th Canadian Conference on Computational Geometry, 2001.
We prove NP-hardness of a wide class of pushing-block puzzles similar to the
classic Sokoban, generalizing several previous results [5,6,9,10,15,17]. 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. The puzzle variants differ in the number of blocks
that the robot can push at once, ranging from at most one
(PUSH-1) up to arbitrarily many
*). Other variations were introduced to make
puzzles more tractable, in which blocks must slide their maximal extent when
pushed (PUSHPUSH), and in which the robot's path
must not revisit itself (PUSH-
X). We prove that
all of these puzzles are NP-hard.
- This paper is also available from ScienceDirect.
- The paper is 19 pages.
- The paper is available in PostScript (497k), gzipped PostScript (133k), and PDF (289k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- PushXCCCG2001 (Pushing Blocks is NP-Complete for Noncrossing Solution Paths)
- Related webpages:
- Pushing Blocks
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 13, 2019 by