A Sokoban room is a grid of walls and floor, a few crates, a pusher and a set of target squares. Push every crate onto a target and the room is done. Deciding whether any sequence of pushes finishes a given room is PSPACE-complete, which Joseph Culberson proved in a technical report at the University of Alberta in 1997.
PSPACE is the set of problems a machine can settle while using an amount of memory bounded by a polynomial in the size of the input. Culberson's construction makes the room simulate a linear bounded automaton, a Turing machine whose tape is exactly as long as its input. The pusher plays the head, the crates carry the tape's symbols, and the room has a solution precisely when the machine halts in an accepting state.
NP sits inside PSPACE, so a PSPACE-complete problem is NP-hard as well; the class is wider rather than a higher tier. What separates Sokoban from the problems in NP is the certificate. A short solution is a certificate anyone can check quickly, and the reduction builds rooms whose solution takes exponentially many moves, so there is no short certificate to look for. The room has to be searched, not guessed and verified.
Culberson's reduction: a linear bounded automaton made of crates
The report is TR97-02, and its abstract states the claim plainly: Sokoban can emulate a linear bounded automaton, and the constructed level has a solution if and only if the machine halts and accepts. When it does halt, the pusher makes on the order of n + t(n) moves and pushes, where n is the number of input symbols and t(n) is the number of machine transitions. The same construction makes the game hard to design as well as hard to solve, because the rules that drive it are three short sentences: you push, you never pull, and a crate you shove against a wall can only travel along that wall.
The result settled a question other people had raised rather than answered. Dorit Dor and Uri Zwick had shown the family of motion planning problems hard in a weaker sense, and Culberson's reduction put the base game at PSPACE-complete. Erik Demaine's survey of pushing-block puzzles collects the family under two bounds: every variant is at least NP-hard and none is above PSPACE, with the exact class moving as the rules change.
Why a fourth crate multiplies the search by twenty-four
The proof is about arbitrarily large rooms. A room you can draw on one screen is a different question, and it can be counted directly. In a room with 100 free cells, placing b crates can be done in C(100, b) ways and the pusher can stand in 100 places, so the pair gives C(100, b) x 100 room states. That is an upper bound, since crates cannot share a cell and a crate cannot sit inside another, but the arithmetic does not care and it makes the shape of the growth obvious.
| Crates | Ways to place them | Room states | Growth from the row above |
|---|---|---|---|
| 2 | 4,950 | 495,000 | — |
| 3 | 161,700 | 16,170,000 | x32.7 |
| 4 | 3,921,225 | 392,122,500 | x24.3 |
| 5 | 75,287,520 | 7,528,752,000 | x19.2 |
| 6 | 1,192,052,400 | 119,205,240,000 | x15.8 |
Two crates and six crates are not the same game with more pieces. The count is near half a million at two crates and past a hundred billion at six, and the multiplier per extra crate only falls from 32 to 16, which is nowhere near fast enough to make a seventh crate reasonable. This is the practical reading of the complexity result: the hardness is not a property of the rules in the abstract, it is a property of how quickly the state count leaves the range where anything can be checked.
The rooms on the Block Push page sit deliberately at the small end of that table. There are sixteen of them, with one, two or three crates each, on boards of between 21 and 88 free cells. The largest room in the set is The Warehouse, 88 cells and two crates, which is 336,864 states by the same bound. The Hourglass has two crates on 79 cells, 243,399 states, and a shortest solution of 62 moves — small enough to solve exactly, and still long enough that working the route out by hand takes a while.
The two counts that decide whether a room is any good
Every room therefore has two numbers attached to it, and they measure different things. The first is the size of the state space, which decides whether the room can be verified at all. The second is the length of the shortest solution, which decides whether the room is worth playing.
| Room | Crates | Free cells | State bound | Shortest solution |
|---|---|---|---|---|
| Zigzag | 1 | 77 | 5,929 | 16 moves |
| Back Room | 1 | 87 | 7,569 | 26 moves |
| The Hourglass | 2 | 79 | 243,399 | 62 moves |
| Three Deep | 3 | 81 | 6,910,920 | 48 moves |
The two columns do not agree with each other, which is the useful part. Three Deep has the largest state bound of the four and a shorter optimal path than The Hourglass, because three crates in an open room are easier to route than two crates in a tight one. Sorting rooms by crate count, by state count, or by the shortest solution produces three different orders, and none of them is a difficulty rating.
What the hardness result buys a level designer
Read forwards, PSPACE-completeness says no fast algorithm will decide whether an arbitrary room can be finished. Read backwards, it says something more useful to anyone building a puzzle game: do not try to generate rooms automatically, because the generator would have to answer the question the proof says is intractable. Sixteen hand-built rooms is not a shortcut around tooling, it is the only design that avoids needing any.
Verification is the one part that does survive, because a single room is small enough for an exhaustive search. Each room here was run through a breadth-first search over full move-states with a visited set and corner-deadlock pruning while it was being made, and the par figure shown on screen is that search's answer rather than a guess. The solver is not shipped with the game; only its results are.
Undo is the other thing the analysis forces. A crate pushed into a corner that is not a target is stuck there for good, and if a target needed that crate then the room is already lost. On a large board that failure is a decision problem in its own right, and on a small one it is a player noticing four moves later. A history of the pusher's previous positions costs little next to the room state count, which is why undo here rewinds the counters along with the crates. The forgiving-input idea behind coyote time and input buffering is the same trade in a different genre; the crate version of it is simply an unbounded stack.
The same wall, hit from the other side
The pattern is not unique to crates. Whenever a puzzle asks for a solution rather than a verification, the hard version of it tends to sit above NP, and designers end up hand-building examples and proving them with a search that only works because the examples are small. A different instance of that trade is the fixed route through the Hamiltonian cycle that makes Snake survivable, where a construction replaces a search nobody can afford to run at speed.
Pros and cons
Pros
- The complexity result is a design constraint that pays for itself: keep rooms small and verifiable, and the level count stays honest.
- An offline breadth-first search over one room gives a real shortest solution, so par is a measured number rather than a settled-on one.
- Unlimited undo costs a stack of positions, which is trivial next to a state space that reaches millions of entries in a three-crate room.
Cons
- Hand-built rooms do not scale: every level needs its own exhaustive search and a human pass, so the count of rooms is a direct measure of hours spent.
- Corner deadlocks are a few lines to detect and the rest are not, so a cheap prune still misses the arrangements where two crates seal a corridor between them.
- No fast exact difficulty measure exists, so any ordering of the rooms by crate count or by par is an approximation presented as a ranking.
Sources
- Sokoban is PSPACE-complete, TR97-02 — Culberson's 1997 technical report at the University of Alberta, including the linear bounded automaton reduction and the n + t(n) move count.
- Dor and Zwick, SOKOBAN and other motion planning problems — the 1999 paper in Computational Geometry: Theory and Applications that shows the decision problem corresponding to Sokoban is NP-hard.
- Pushing blocks: a survey of the hardness results — Erik Demaine's collection of the crate-pushing family, with the NP-hard lower bound and the PSPACE upper bound for every variant.