Erik Demaine's Combinatorial Games:

Pushing Blocks

Categorization

Pushing-block puzzles are a popular form of one-player game in which an agent or robot moves around and pushes unit-square obstacles in a square grid. There are several variations on the rules, depending on the following aspects:
  1. The strength of the robot: How many blocks can the robot push at once?
  2. Can blocks be tied to the board, making them unpushable?
  3. How far do blocks move when pushed? Typically blocks move only one space at a time, but in the more icy/frictionless model of PushPush, blocks slide as far as possible.
  4. What is the goal of the robot? There are two common targets:
    1. The robot should reach a particular position (the exit), as in the various Push puzzles.
    2. The movable blocks should all be placed on marked (but undistinguished) target squares, as in the Sokoban puzzle.
  5. Various restrictions can be placed on the solution path. In particular, what if the robot is not allowed to revisit any square?

Complexity

Since 1991, basically all variations of pushing-block puzzles have been explored from the point of view of computational complexity. The short summary is that pushing blocks is at least NP-hard and at most in PSPACE, no matter which combination of parameters you choose. The main open questions are whether various versions are in NP or PSPACE-complete.

Surveys on these results can be found in most papers on the subject, in particular the latest Push-X paper and the preceding Push-1 paper; as well as in my survey paper on combinatorial games and puzzles. I also give a brief overview here.

Versions

Sokoban

Perhaps the best-known example of a pushing-block puzzle is the computer game Sokoban. Here (1) the robot can push only one block at a time, (2) blocks can be tied to the board, (3) blocks move only one space at a time, and (4) the goal is to place the movable blocks on specified target locations (but any block can be placed on any target). This game was invented by Hiroyuki Imabayashi of Thinking Rabitt Co. in 1982; see a history of Sokoban.

There are many implementations of Sokoban and puzzles available, most of which are freely available. For example:

NP-hardness of Sokoban was established by Dorit Dor and Uri Zwick in their 1995 paper “SOKOBAN and other motion planning problems”, appearing in Computational Geometry: Theory and Applications, volume 13, number 4, 1999, pages 215--228. PSPACE-completeness was established by Joseph Culberson in his 1997 paper “Sokoban is PSPACE-complete”, appearing in Proceedings of the International Conference on Fun with Algorithms, June 1998, pages 65-76.

Origins

The formal study of robot-manipulation puzzles was initiated by Gordon Wilfong in 1991. He proved NP-hardness of a variation not captured by the categorization above, in which L-shaped pieces can be both pushed and pulled by the robot.

Push[Push]-1/k/*-[X]

The formal study of square-block-pushing puzzles was initiated by Arundhati Dhagat and Joseph O'Rourke in 1992. They proved NP-hardness of a version that has since been dubbed Push-* with fixed blocks. In general, there are many variations under the "Push" umbrella:
  1. In Push...-1, the robot can push only one block at once, and more generally in Push...-k the robot can push at most k blocks at once, whereas in Push...-*, the robot has the strength to push any number of blocks.
  2. There are two versions of every puzzle, in which either blocks can be tied to the board (with fixed blocks) or not (without fixed blocks). This issue is particularly relevant in Push...-*, although it may make a difference even in Push-k where a (k+1)-by-(k+1) square of blocks is effectively immobile.
  3. In Push-... blocks move only one square at a time, whereas in PushPush-... blocks slide to their maximal extent.
  4. The goal of the robot is to reach a particular target location.
  5. In the Push...-X variation, the solution path is not allowed to cross itself.
Thus, the 16(+) puzzles are Push-k, Push-*, PushPush-k, PushPush-*, Push-k-X, Push-*-X, PushPush-k-X, PushPush-*-X, all with or without fixed blcoks.

While there are various papers proving NP-hardness of specific versions (see the surveys cited above and in particular the webpages cited below), the NP-hardness of all of these puzzles can be established by just the latest two papers:

I have seperate webpages on two flavors of Push puzzles, which describe joint work with Martin Demaine and Joseph O'Rourke:

Last updated November 28, 2010 by Erik Demaine.