Sokoban is NP-hard: why AI can't solve your puzzle
Building Push Box, I considered adding an "auto-solve" button like Sudoku. Quick research told me: can't be done. Sokoban is formally proven NP-hard — actually PSPACE-complete — in computer science. This article unpacks why.
What "NP-hard" and "PSPACE-complete" mean
These terms sound intimidating. Plain-English versions:
NP-hard: this problem is "at least as hard as every NP problem." The most famous NP problem is the Traveling Salesman (shortest tour through N cities) — the fastest known algorithm is exponential O(2^N). NP-hard means a problem is at least as hard as TSP.
PSPACE-complete: the worst. Not just exponential time, but exponential space (memory) as well. Meaning: even with infinite time, you might fail with finite memory.
Sokoban was proven PSPACE-complete by Joseph Culberson in 1997. The proof method: showed you can convert any PSPACE-complete problem (like a linear bounded automaton) into a Sokoban level. Once convertible, Sokoban is at least as hard.
What it actually means
By numbers. Push Box level 6 is roughly 10x8 board + 4 boxes + 4 targets. The state space (all player+box position combinations) is:
player position × C(40, 4) × ... ≈ 1 billion states
Level 10 has ~50 cells + 7 boxes. State space blows up to trillion-scale. A normal computer with the best search algorithms (IDA* + many heuristic prunings) takes minutes to hours. Scale up further (like XSokoban's 100-box classic puzzles) and the best solvers still haven't fully solved every one.
For comparison:
- 9x9 Sudoku: state space ~10^21, but constraints are so strong that backtracking solves in milliseconds
- 5x5 Lights Out: state space 10^7, GF(2) linear algebra solves instantly
- Sokoban 8x8 with 4 boxes: state space 10^9, requires a professional solver minutes
What's the difference? Sudoku's moves are "locally independent" — placing a number has limited effect elsewhere. Sokoban's box pushes change global reachability — pushing one box can permanently lock another out of its target. This global coupling is the root of PSPACE-completeness.
Why does such a "simple" game become so hard?
This is Sokoban's most fascinating property. The rules are 3:
- Player moves one cell
- Player can push one box (not pull)
- Box on target = scored
3 rules, 5 minutes to teach a 7-year-old. The hardness comes from —
Irreversibility. Most games' moves are undoable (walk wrong, walk back). Sokoban is "semi-reversible": your feet retreat, but a box once pushed can only be moved from the opposite side. Pushed into a corner, it's permanently stuck — that's a "deadlock."
Box coupling. Pushing box A changes your position, which affects which sides you can approach other boxes from. Two boxes can block each other — A must be pushed before B, but B can only be pushed if A moves first. This circular dependency kills local decision-making.
Does this mean "no AI solver possible"?
No. It only means "the worst case is impossible." In practice, most Sokoban puzzles are solvable by modern solvers because human-designed levels have "reasonableness" — designers avoid the worst PSPACE instances to keep puzzles playable.
Modern Sokoban solver techniques (Festival, Takaken):
- IDA* search: iteratively deepening A*
- Zone analysis: partition board into zones, solve in pieces
- Deadlock detection: heuristically detect "if I keep pushing, I'll deadlock," prune immediately
- Hash memoization: record visited states, avoid revisits
- Box-line optimization: find "closed paths" for boxes as sub-goals
These together solve 80%+ of "human-difficulty" puzzles. But classics (e.g., XSokoban #50) remain unsolved automatically.
Computational complexity tells you "how hard the worst case is." Real puzzles aren't usually worst case. But your solver must leave room for the worst case.
How BverGame's Push Box does it
I designed 10 levels by hand. I tested all of them myself to confirm solvability. Average optimal step count: 15-60. Each level has a "main solution" but allows variants.
What I did not add:
- Auto-solve feature — explained above. The hardest level could make browser JS run for minutes
- Dynamic level generation — harder than hand design. Generating "solvable, challenging, not boring" random levels is itself an NP-hard problem
- "Undo before deadlock" feature — deadlock detection is its own research area. I settle for unlimited undo and reset
On demystifying "AI solves puzzles"
Today's LLMs like ChatGPT are often hyped as "puzzle solvers." In reality, ask ChatGPT to solve an 8x8 Sokoban — most likely it'll produce a plausible but wrong solution. Because LLMs aren't searchers; they're statistical models predicting the next token.
Real solvers are dedicated algorithms. Compare ChatGPT against Festival (2020 Sokoban solver): the former is a toy; the latter conquers expert puzzles in hours.
So next time someone says "AI can solve any puzzle," remember Sokoban as the counterexample.
Lessons for players
Knowing this won't let you pass levels faster, but gives you mental backup when stuck:
1. Stuck doesn't mean you're dumb. The game is mathematically hard; human brains aren't optimized for PSPACE-complete problems.
2. Trial-and-error is rational. Without an obvious optimal algorithm, lots of undo and retry is necessary. Push Box's undo is unlimited; use it freely.
3. Think in chunks. Pro human players break a level into "sub-levels," focusing on 1-2 boxes at a time and treating others as "still." This matches solver "zone analysis."
Closing
Sokoban is a deceptively simple, deeply rich toy. Invented by Hiroyuki Imabayashi (Japan, 1981). 40+ years later it's still an active topic in computational complexity research.
Next time you're stuck on Push Box level 7, remember: you're wrestling with a PSPACE-complete problem. Being stuck is the nature of the problem.
Step back, look at the whole board, ask: can this box still come out of that corner? If not, don't push it.
Leo is BverGame's co-engineer. Reference: Joseph Culberson, "Sokoban is PSPACE-complete" (1997). For solver state-of-the-art, see sokobano.de and community resources.