Mastering Sokoban: Deadlock Avoidance and Path Planning

Sokoban is a 1981 puzzle game by Hiroyuki Imabayashi. A warehouse keeper pushes crates onto target squares. Crates can only be pushed, never pulled, which makes most “obvious” moves wrong. Mastering Sokoban means recognizing deadlock states before you create them, planning the push order so every crate reaches a target, and learning the patterns that recur across thousands of community-built levels. Pure puzzle, no reflexes.

The rules in one paragraph

You control a keeper on a grid of floor squares, walls, and target marks. Crates sit on some floor squares. You move the keeper in four directions; pushing a crate moves it one square in the direction you walked into it, but only if the square the crate is moving into is empty floor. Crates cannot be pulled. Pushing two crates at once is illegal — the keeper can only push one crate at a time, and only if there is room behind that crate. Win when every target square has a crate on it.

Deadlock recognition

A deadlock is a board state from which the puzzle cannot be solved no matter what you do. Sokoban deadlocks come in patterns.

Corner deadlocks

A crate pushed into a corner (two walls meeting at a right angle) cannot be moved off the corner. You cannot pull, so the crate is stuck. If the corner is not a target square, that crate can never reach a target. Deadlock.

This is the simplest and most common deadlock. Every “I pushed the crate the wrong way” mistake in Sokoban is usually a corner deadlock.

Wall-line deadlocks

A crate pushed against a wall along a long line, with no perpendicular escape, can become stuck even without a corner. The crate can slide along the wall but cannot leave the wall. If no target square exists along that wall line, the crate is dead.

Example: a crate pushed against the top wall in a corridor with no openings on the bottom side. The crate can move left or right along the wall, but it cannot go up (wall) or down (we cannot pull). If there are no targets on the top wall, the crate is dead.

Two-crate freezes

Two crates pushed against a wall in adjacent positions can freeze each other. Imagine two crates A and B on the same wall, A to the left of B. Pushing A right is blocked by B. Pushing A left moves A only if there is room. Pushing B right or left is similar. If neither crate has independent escape, both are stuck.

This pattern is subtle. The deadlock can occur even when each crate individually looks free.

Box-on-target false positives

Sometimes a crate sits on a target square but the position is still deadlocked because of other crates. A crate on a target is not always safe — if it blocks the only path for another crate to reach another target, you have to push it off.

This is why Sokoban requires planning the whole solution, not just finishing one crate at a time.

Path planning

The keeper’s path from one position to another matters. To push a crate east, the keeper must approach the crate from the west. If the west side of the crate is blocked by a wall or another crate, you cannot push east.

Plan path-of-the-keeper, not just path-of-the-crate. Before pushing crate A toward its target, check that the keeper can get to every push side of A along the way without first needing to push another crate.

For complex levels, the keeper’s reachable squares change every push (because crates are obstacles). Computer Sokoban solvers represent the state as “crate positions plus the set of squares the keeper can reach”; that representation captures every meaningful distinction.

Push order

Most Sokoban levels have multiple crates to place. The order matters because each push changes what is reachable.

Reverse-planning works well:

1. Identify the target squares that are hardest to reach (deep in a corner, behind a wall section).
2. Determine which crate must end on each hard target.
3. Plan that crate’s push sequence first; place it last only if other crates would block its final approach.
4. Plan the easier crates’ sequences around the hard one.

The intuition: if a corner target needs a crate, and the corridor leading to it is narrow, the crate placed there must be the last to enter that corridor. Place easier crates first, then weave the corner-target crate through.

Look-ahead

Before any push, ask three questions:

1. Does this push reach a target or move the crate closer to one?
2. Does this push create a deadlock (corner, wall-line, freeze) for this crate?
3. Does this push block another crate’s path to its target?

The third question is the one casual players skip. A push that looks fine for the current crate can strand another crate in a now-unreachable area.

Strong play uses 3-5 moves of look-ahead. Solver tools use much deeper search, but human play with 3-5 moves of mental simulation already filters out most blunders.

The undo button

Almost every Sokoban implementation includes unlimited undo. Use it. The skill is not in playing the level without mistakes; it is in identifying mistakes quickly and undoing them.

Some Sokoban purists practice “no-undo” runs once they have solved a level by undo, but for learning new levels, the undo button is the right tool. The puzzle is the planning, not the execution.

Level design patterns

Reading Sokoban levels gets easier once you recognize the common design templates.

• Conveyor: a row of crates that must be pushed across a corridor to a row of targets. The order of pushes matters because each pushed crate frees space for the next.
• Storage room: a large open area with several targets. The constraint is the size of the keeper’s path; reaching each push position requires moving around other crates.
• Corner puzzle: one or more targets in corners. The corner crates must arrive last so they do not block their own approach.
• Switching puzzle: two crates must end on each other’s “wrong” targets after moving past each other. Requires using a side branch as a buffer.

Most large Sokoban levels are composed of multiple such patterns. Recognizing them speeds up planning.

Solving classic level packs

Several public-domain level packs are the standard practice material:

• The original Imabayashi levels (1981-82), 50 levels included in the original release.
• The Sasquatch series by David Skinner, large and difficult.
• The XSokoban collection bundled with many open-source implementations.
• Sokomind Plus and the recent Yoshio Murase compilations.

Start with the original Imabayashi 50 (which start very easy and ramp up). Move to community packs once those feel routine.

Common mistakes

• Pushing crates into corners thoughtlessly. If the corner is not a target, the crate is dead.
• Solving one crate at a time without checking the others. A crate on its target can block the only path for another crate.
• Ignoring keeper reachability. The keeper has to physically get to each push position.
• Not undoing mistakes. Pushing on after a wrong move wastes the level; undo and replan.
• Forgetting the wall-line freeze. A crate pushed along a wall can be deadlocked even without a corner.

How to practice

Online Sokoban implementations are abundant. The Sokoban YASC client and the SokoFan portal both let you play hundreds of community level packs with undo and hint support. Many mobile apps offer curated daily puzzles.

For the history (Imabayashi created Sokoban for Thinking Rabbit’s 1981 launch, and the game has been ported to nearly every platform since) and the computer-science background (Sokoban is PSPACE-complete in the general case), the Wikipedia article on Sokoban is a solid reference. For similar puzzle games, see our games like Sokoban guide.

Frequently asked questions

Is Sokoban computationally hard?

Yes. Sokoban is PSPACE-complete in the general case, which means worst-case levels can require an enormous search to solve. Practical levels are usually solvable by humans because the design includes recognizable patterns.

What is a deadlock in Sokoban?

A deadlock is a board state from which the puzzle cannot be solved no matter what you do. The most common deadlock is a crate pushed into a corner that is not a target. Wall-line freezes and two-crate freezes are common as well.

Why can’t you pull crates in Sokoban?

The original rules only allow pushes. The puzzle’s difficulty comes from this restriction — many crate moves would be trivial if pulling were allowed. The “Sokoban+” variant allows pulls but is a different puzzle.

Should you use undo in Sokoban?

Yes. Sokoban is a planning puzzle, and undo is the standard tool for trying alternatives. Most implementations support unlimited undo. Some players practice no-undo runs after solving a level, but for new puzzles, undo is the right approach.

What is the original Sokoban level set?

The original 1981 release by Thinking Rabbit included 50 levels designed by Hiroyuki Imabayashi. These remain a standard introduction to the game and ramp from easy to moderately challenging.

The bottom line

Mastering Sokoban is deadlock recognition plus path planning. Every push is reversible only through undo, so look ahead, plan the order, and avoid the corner and wall-line traps. The patterns become automatic with practice. When you need a break from crate-pushing, the Chrome Dino game is in the next tab — no planning required.