Erik Demaine's Pushing Blocks:

Push-1

Push-1 is a pushing-blocks game with the following rules:
  1. Initially, the planar square grid is filled with some unit-square blocks (each occupying a cell of the grid) and the robot placed in one cell of the grid.
  2. The robot can move to any adjacent free square (without a block).
  3. The robot can push any adjacent block, moving it one square in the pushed direction.
  4. The goal is to get the robot to a particular position.
The algorithmic Push-1 problem is to decide whether a given puzzle is solvable.

Complexity

Martin Demaine, Joseph O'Rourke, and I have proved that the Push-1 decision problem is NP-hard. This is described in our paper, “PushPush and Push-1 are NP-hard in 2D”. Our reduction also happens to apply to a related pushing-blocks game, PushPush.

It remains open whether Push-1 is in NP (e.g., every puzzle has a polynomial-length solution path) or PSPACE-complete.

Last updated November 28, 2010 by Erik Demaine.