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.

BibTeX

@InProceedings{Push2F_CCCG2002,
  AUTHOR        = {Erik D. Demaine and Robert A. Hearn and Michael Hoffmann},
  TITLE         = {Push-2-{F} is {PSPACE}-Complete},
  BOOKTITLE     = {Proceedings of the 14th Canadian Conference on Computational
                   Geometry (CCCG 2002)},
  bookurl       = {http://www.cs.uleth.ca/cccg},
  ADDRESS       = {Lethbridge, Alberta, Canada},
  MONTH         = {August 12--14},
  YEAR          = 2002,
  PAGES         = {31--35},

  LENGTH        = {5 pages},
  dblp          = {https://dblp.org/rec/conf/cccg/DemaineHH02},
  COMMENTS      = {This paper is also available from the
                   <A HREF="http://www.cs.uleth.ca/~wismath/cccg/proceedings/">
                   electronic proceedings</A> as
                   <A HREF="http://www.cs.uleth.ca/~wismath/cccg/papers/31.ps">http://www.cs.uleth.ca/~wismath/cccg/papers/31.ps</A>.
                   <P>
                   This version is updated from the <A HREF="old.ps">original
                   conference version</A> in order to fix an error discovered
                   in January 2003.},
  unrefereed    = 1,
  withstudent   = 1,
  ee            = {http://www.cs.uleth.ca/\%7Ewismath/cccg/papers/31.ps},
}

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]