Paper by Erik D. Demaine

Erik D. Demaine, Robert A. Hearn, and Michael Hoffmann, “Push-2-F is PSPACE-Complete”, in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002, pages 31–35.

We prove PSPACE-completeness of a class of pushing-block puzzles similar to the classic Sokoban, extending several previous results [1, 5, 12]. The puzzles consist of unit square blocks on an integer lattice; some of the 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 just one (Push-1-F) up to arbitrarily many (Push-*-F). We prove that Push-k-F and Push-*-F are PSPACE-complete for k ≥ 2 using a reduction from Nondeterministic Constraint Logic (NCL) [8].

This paper is also available from the electronic proceedings as

This version is updated from the original conference version in order to fix an error discovered in January 2003.

The paper is 5 pages.

The paper is available in PostScript (899k), gzipped PostScript (185k), and PDF (221k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 16, 2024 by Erik Demaine.