Paper by Erik D. Demaine

Reference:

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.

BibTeX

@InProceedings{PushPush1_PSPACE_FUN2004,
  AUTHOR        = {Erik D. Demaine and Michael Hoffmann and Markus Holzer},
  TITLE         = {{PushPush}-$k$ is {PSPACE}-Complete},
  BOOKTITLE     = {Proceedings of the 3rd International Conference on Fun with
                   Algorithms (FUN 2004)},
  bookurl       = {http://www.di.unipi.it/fun04/},
  MONTH         = {May 26--28},
  YEAR          = 2004,
  ADDRESS       = {Isola d'Elba, Italy},
  PAGES         = {159--170},

  length        = {12 pages},
}

Abstract:

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

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (471k), gzipped PostScript (97k), and PDF (160k).

See information on file formats.

[Google Scholar search]