Push-1
Push-1 is a pushing-blocks game with the following rules:
- 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.
- The robot can move to any adjacent free square (without a block).
- The robot can push any adjacent block, moving it one square in the
pushed direction.
- 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.