PushPush
PushPush (or PushPush-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, and that block slides in that
direction to the maximal extent possible, i.e., until the block is
against another block.
- The goal is to get the robot to a particular position.
The algorithmic PushPush problem is to decide whether a given puzzle is
solvable.
History
This definition is inspired by a computer game called PushPush,
which was invented by Alan Rogers in 1991.
In turn, PushPush was inspired by the more-arcade less-puzzle game Roll-Out
written for the Amiga by Olaf Schneider in 1989.
[Thanks to Alan for this historical information.]
Alan Rogers and C.M. Mead III wrote the
original
Macintosh version of PushPush in 1994.
In 2002, they put up pushpush.net
which includes a Flash version of the game (including the original levels)
as well as links to other implementations.
For example, a
version
for the Amiga was written by Luigi Recanatese in 1997.
This page describes the known theoretical results and open problems about
PushPush, and includes an implementation.
Complexity
The first paper about this problem is “PushPush is NP-hard in 3D” by
Joseph O'Rourke and
The Smith Problem Solving Group. This paper shows that the decision problem
is NP-hard for PushPush in 3D, i.e., PushPush played on a 3-dimensional cube
grid. The paper is available as
cs.CG/9911013
of the Computing Research
Repository (CoRR).
Building on this work, Martin Demaine,
Joseph O'Rourke, and I
have proved that the decision problem for the original PushPush problem
(in 2 dimensions) is NP-hard. This is described in our paper,
“PushPush is NP-hard in 2D”.
We developed another NP-hardness reduction so that it is suitable for both
PushPush and a related game,
Push-1, in our paper
“PushPush and Push-1 are NP-hard in 2D”.
It is open whether this problem is in NP, in particular whether every solvable
puzzle has a polynomial-length solution path. It is also open whether it is
PSPACE-hard.
Implementation
Using Mark Overmars's
wonderful Game
Maker, it was easy to implement PushPush. This implementation will run
on any platform that Game Maker supports, which is currently only a
Microsoft Windows environment. My implementation is free, as is Game Maker.
In order to use it, you will have to download and install
Game Maker;
download the PushPush ZIP file; then uncompress
this into the Game Maker/Games directory.
Running Game Maker and selecting the "Erik PushPush" game will allow you to
play or edit the game. The built-in puzzles are not really puzzles; rather,
they illustrate all the gadgets in the hardness reduction in our paper.
If you design any puzzles, please send them to me and I will add them
(with due credit). Have fun!