Paper by Erik D. Demaine

Reference:

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.

Abstract:

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].

Comments:

This paper is also available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/31.ps.

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

Length:

The paper is 5 pages.

Availability:

The paper is available in PostScript (899k), gzipped PostScript (185k), and PDF (221k).

See information on file formats.

[Google Scholar search]