Erik Demaine's Pushing Blocks:

PushPush

PushPush (or PushPush-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, and that block slides in that direction to the maximal extent possible, i.e., until the block is against another block.
  4. 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!

Last updated November 28, 2010 by Erik Demaine.