Sokoban

Sokoban (倉庫番, “warehouse keeper” in Japanese) is the 1981 puzzle game by Hiroyuki Imabayashi that essentially invented the box-pushing puzzle genre. The premise: a small worker character must push boxes onto target positions in a warehouse. You can only PUSH boxes — never pull. You can only push ONE box at a time, never two stacked. The game’s apparent simplicity hides remarkable depth — solving Sokoban levels in general is NP-hard (in fact PSPACE-complete), and academic computer science has studied them as benchmarks for AI planning algorithms.

How to play

• Arrow keys or WASD (or swipe on a touchscreen) — move the worker in 4 directions (up/down/left/right).
• Boxes are pushed when you walk into them. You can only push, never pull.
• You can push ONE box at a time, never two stacked together.
• Push every box onto a target square (marked with a green dot; a box turns green when it’s on a target) to solve the puzzle.
• Walls block both you and boxes.
• If a box gets pushed into a corner with no target, the puzzle is unsolvable from that state — undo (U) or restart (R).
• There are 15 levels; pick any from the level menu, or press N / Next Level after a solve. Your fewest moves for each level is saved in your browser.

Beginner strategy

• Plan before pushing. Once you push a box into a corner or against a wall, you might be unable to move it again.
• Identify dead positions. A box in a corner (with no target on that corner) is permanently stuck. Don’t push boxes into corners.
• Solve the hardest box first. Some boxes have only one path to their target. Solve those first — the others have more flexibility.
• Reverse-think the solution. Instead of “how do I push box X to target Y”, think “what’s the LAST push that places box X on target Y? What state must precede it?”
• Use undo liberally. Sokoban is about planning. Undo lets you experiment.

Dead-position analysis

• Corner deadlock. Box in a corner with no target there = unsolvable.
• Wall deadlock. Box pushed against a wall with no target on that wall AND no perpendicular escape route = stuck.
• Two-box deadlock. Two boxes side-by-side along a wall can lock each other in place.
• Square deadlock. Four boxes and walls forming a 2×2 block can never move again, so it’s stuck unless every box in it is already on a target.
• Recognize these patterns instantly. Avoiding deadlocks is the core skill.

Intermediate strategy

• Pre-solve target order. Decide which box goes on which target before pushing anything. Often only one assignment is feasible.
• Solve “free” boxes last. Boxes that can reach multiple targets give you flexibility — save them for cleanup.
• Mark dead squares mentally. Squares that can never hold a box (because pushing onto them locks the box) should be visualized as “off-limits”.
• Use side-paths. Sometimes the route to push a box requires you to walk around the box on a different path first.
• Don’t be afraid to retreat. Some Sokoban puzzles require pushing a box partway, then walking away to push another box, then returning to finish the first.

Advanced strategy and complexity

• Sokoban is PSPACE-complete. Generalized Sokoban (arbitrary level layouts) is PSPACE-complete (Culberson, 1997). Determining if a level is solvable is computationally equivalent to the hardest problems in space-bounded computation.
• Solver-friendly puzzles vs solver-hostile. Well-designed Sokoban puzzles have unique or near-unique solutions that humans can find by reasoning. Many computer-generated puzzles are extremely hard for both humans and solvers.
• State-space size. A 10×10 Sokoban with 5 boxes has ~10^8 possible states. Solvers use heuristics (e.g. distance from box to nearest target) to prune.
• Pattern databases. Advanced solvers precompute solutions for sub-states (which boxes-and-target-assignment subsets are reachable from where) — similar to chess endgame tables.
• Big puzzles with dozens of boxes exist, and dedicated solvers work through them over many sessions. Most casual players need hints or trial-and-error past 10-15 boxes.

Sokoban’s history

• 1981-82 — Hiroyuki Imabayashi creates Sokoban. Published by Thinking Rabbit in 1982 on Japanese personal computers (NEC PC-8801).
• 1988 — Soko-Ban in the West: Spectrum HoloByte publishes versions for IBM PC, Apple II and Commodore 64.
• 1989-90 — console versions: Boxxle on Game Boy and Boxyboy on TurboGrafx-16 bring the puzzle to console audiences.
• 1990s — academic interest: Sokoban becomes a standard benchmark for AI planning research.
• 1997 — Culberson proves PSPACE-completeness. Formally establishes Sokoban’s computational complexity.
• 1990s-2000s — internet Sokoban communities: XSokoban, David W. Skinner’s Microban and Sasquatch level sets, the Sokoban Wiki.
• 2010s — mobile Sokoban apps: hundreds of levels in your pocket.
• 2015-2022 — Snakebird, Patrick’s Parabox: modern indie successors that push the Sokoban idea further with new mechanics.

Why Sokoban is loved

• Pure planning. No reflexes, no time pressure. Just spatial reasoning.
• Aha-moment satisfaction. Each solution feels earned.
• Scalable difficulty. Beginner puzzles take 30 seconds; expert puzzles take hours.
• Infinitely replayable. Thousands of puzzles available online, with new ones daily.
• Solver-friendly format. Sokoban puzzles serialize as text files — easy to share, easy to solve programmatically.

Common mistakes

• Pushing first, thinking second. Random exploration creates deadlocks. Plan multi-move sequences.
• Ignoring corner deadlocks. A box in a non-target corner is a guaranteed restart.
• Solving boxes in obvious order. Sometimes the first-targeted box should be solved LAST.
• Quitting on hard puzzles. Most Sokoban puzzles are solvable with patience. Take a break, then return with fresh eyes.
• Not using undo. Undo is your friend. Experimentation is the path to insight.

Sokoban variants and modern descendants

• Snakebird (2015). Sokoban with growing snakes; bend constraints.
• Patrick’s Parabox (2022). Sokoban with recursive boxes inside boxes.
• Stephen’s Sausage Roll (2016). Acclaimed Sokoban-style puzzler with grilling sausages.
• Helltaker (2020). Sokoban with story and a limited number of moves per level.
• Baba Is You (2019). Sokoban where game RULES are themselves pushable.
• A Monster’s Expedition (2020). Sokoban with chopping trees as the puzzle medium.

FAQ

• Q: Can I pull boxes? A: No — only push. This single restriction is what makes Sokoban hard.
• Q: Can I push two boxes at once? A: No — only one. Two stacked boxes can’t be pushed.
• Q: How do I undo? A: Press U or the Undo button to step back, up to 200 moves. R or Restart resets the level.
• Q: How many puzzles exist? A: Thousands. Most are generated by humans for puzzle collections. The Sokoban community maintains large level collections, many with known optimal solutions.

For other puzzle games, try Tower of Hanoi, 15 Puzzle, Sudoku, or Lights Out.