- The strength of the robot: How many blocks can the robot push at once?
- Can blocks be tied to the board, making them unpushable?
- 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.
- What is the goal of the robot? There are two common targets:
- The robot should reach a particular position (the exit), as in the various Push puzzles.
- The movable blocks should all be placed on marked (but undistinguished) target squares, as in the Sokoban puzzle.

- Various restrictions can be placed on the solution path. In particular, what if the robot is not allowed to revisit any square?

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.

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

- Sokoban, an extensive Windows implementation by Björn Källmark with over 450 puzzles
- SokobanMac, an excellent Macintosh implementation by Scott Lindhurst, plus a repository for hundreds of collected puzzles. [The three images on the right are taken from this webpage.]
- A Java implementation by Pimpernel Online with 20 puzzles
- XSokoban, an X-Windows implementation
- Over 350 puzzles designed by David Skinner
- Puzzles designed by Yoshio Murase and generated by a program of his, including many links to pages and papers on solving Sokoban and generating puzzles by a computer in practice
- Shockoban, a Shockwave implementation
- The Yahoo! Sokoban group contains discussion areas with hints and additional puzzles
- SokoMind, a Windows implementation
by Gerald Holler
that includes a variation (SokoMind Plus) in which each blocks must move
to a
*specific*target location, and a repository of over a thousand puzzles the standard version and this variation - Soko, a Windows implementation by Mark McIntyre that includes a level editor and several new puzzles

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.

- In
**Push...-1**, the robot can push only one block at once, and more generally in**Push...-**the robot can push at most*k**k*blocks at once, whereas in**Push...-***, the robot has the strength to push any number of blocks. - 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. - In
**Push-...**blocks move only one square at a time, whereas in**PushPush-...**blocks slide to their maximal extent. - The goal of the robot is to reach a particular target location.
- In the
**Push...-X**variation, the solution path is not allowed to cross itself.

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:

- “Push-* is NP-hard” by Michael Hoffmann, which handles all Push...-*-... variations.
- “Pushing
Blocks is NP-Complete for Noncrossing Solution Paths”
by Michael Hoffmann and myself, which handles all Push...-
*k*-... variations.

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

- PushPush-1:
Blocks slide as far as possible, and only one block can be pushed at
a time. Includes my computer implementation of this game,
and links to related implementations.
- Push-1: Blocks slide one square at a time, and only one block can be pushed at a time.