# 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!