Paper by Erik D. Demaine
- Erik D. Demaine, Michael Hoffmann, and Markus Holzer, “PushPush-k is PSPACE-Complete”, in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 159–170.
We prove that a pushing-block puzzle called PushPush-k is
PSPACE-complete for any fixed k ≥ 1. In this puzzle,
a robot moves on a finite grid. Each grid position is either empty or
occupied by a single obstacle block. While moving, the robot may
push obstacle blocks in direction of its movement, subject to
certain constraints. In particular, once an obstacle block starts
moving, it continues to do so until it hits another obstacle or the
grid boundary. The problem is to decide whether the robot can
navigate from a given start position to a specified goal position on
- The paper is 12 pages.
- The paper is available in PostScript (471k), gzipped PostScript (97k), and PDF (160k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 2, 2021 by