Sokoban planning and deadlocks
Most puzzles forgive you. Sudoku lets you erase a digit, a sliding puzzle lets you unwind a row, and a word search cannot be damaged at all. Sokoban is the exception on our shelf. Walking is free and reversible — step left, step right, nothing has changed. Pushing is neither. A crate moves away from you and only away from you, and there is no mechanism anywhere in the game for pulling one back.
That asymmetry is the whole design. It means a level can become permanently unsolvable on move four while the board still looks tidy and nothing tells you it happened. You keep playing a puzzle that has already ended. The skill in Sokoban is not dexterity or search speed; it is recognizing the positions that kill a level, and doing your thinking before the push instead of after it.
Reading the diagrams
The diagrams below use the notation that Sokoban players have used for decades:
# wall $ crate @ you . target * crate sitting on a target
The four deadlocks worth memorizing
A deadlock is a position that cannot lead to a solved level. There are many of them in theory, and recognizing all of them is genuinely hard, but four patterns account for nearly every level we have lost. Learn to see these four and your restart rate collapses.
1. A crate in a corner
##### #$ # #@ # # .# #####
The crate sits where two walls meet. To push it right you would have to stand on the square to its left, which is wall. To push it down you would have to stand above it, which is also wall. Nothing can ever move it again, and unless that corner square happens to be a target, the level is finished.
This is the first thing to internalize, because it turns into a habit that costs nothing: before any push, look at the destination square and ask whether it is a corner. Corner squares that are not targets should feel radioactive.
2. A crate flat against a wall that has no target on it
######### # $ # <- pinned against the top wall # @ # # . # <- the only target is not on that wall #########
This one is quieter than the corner and it catches more players. The crate is not stuck: you can still push it left and right along the top wall as much as you like. What you cannot do is get it out of that row, because pushing it down requires standing above it, and above it is wall.
So the crate is confined to a single line for the rest of the level. If that line contains a target, fine — push it there. If it does not, the crate is as dead as one in a corner, and it will keep gliding back and forth looking perfectly healthy while you slowly realize the level is over.
The useful generalization: a crate against a wall can only travel along that wall. Before pushing a crate up against any wall, check whether a target lives somewhere on that wall.
3. A two-by-two square of four crates
####### # # # $$ # # $$ # # @ # #######
No walls are involved here, which is why players walk into it. Four crates in a two-by-two block are mutually frozen: each one has a crate on two of its sides, and on the other two sides the square it would move into is occupied by another crate. Push any of them in any direction and the destination is a crate, which is not a legal push.
The same logic works with fewer crates and some help from walls. Two crates side by side against a wall can be frozen together, and a crate diagonally adjacent to another crate is often the beginning of a block you cannot dissolve. The general rule to carry: crates that touch each other lose mobility, so avoid gathering them unless you are gathering them onto targets.
4. The one-wide corridor you entered from the wrong side
########### #..@$.....# ###########
In a corridor one tile wide, a crate has exactly two possible directions, and which of them you get is decided by the side you approach from. Here you are to the crate's left, so you can only push it right. Getting to its other side would mean walking through it, and there is no route around. If the targets are behind you, the level is already lost — not by a bad push, but by the walk that put you on the wrong side.
This is the deadlock that best illustrates why Sokoban is a planning game. Nothing in the position looks dangerous. No crate is stuck. The mistake was a decision about where you stood, several moves before any crate moved, and the pattern generalizes: in a tight level, your own position is a resource you can spend by accident.
Solve the level backwards, from the targets
The instinct is to start at a crate and look for a route to a target. Reverse it. Start at a target and ask two questions:
- From which square must a crate arrive? A target with walls on two sides can only be entered from one or two directions, which immediately fixes the last push.
- Where must I be standing to make that push? That square is directly opposite the direction of travel, and it has to be reachable at the moment of the push — with all the other crates wherever they will be by then.
Keep stepping backwards from there: the square before that, and the square you stood on before that, until the chain arrives at a crate's starting position. What you have built is the route in reverse, and because you started from the constrained end, the difficult decisions were made first.
Thinking backwards has a second benefit. In reverse, pushing becomes pulling, and pulling has no deadlocks — you can always pull a crate out of a corner. So a route that looks impossible forwards is often obvious backwards, and any route you find by pulling from the targets is guaranteed to be pushable forwards when you play it for real.
A practical version for a level you have never seen: before touching anything, look at every target and sort them by how enclosed they are. Targets in corners and dead ends have one acceptable last push. Targets in open floor have four. The corners are the constraints, and constraints are where planning starts.
Delivery order decides the level
Every crate you deliver becomes a wall. It is a permanent obstruction in the middle of the floor for the rest of the level — you would have to push it off its target to move it, which is usually the beginning of a much worse problem. That single fact makes order more important than route.
- Fill the most enclosed targets first. A target down a dead-end corridor needs that corridor empty. Fill it while you still can, and leave the target sitting in open floor for last, since open floor stays reachable from several directions.
- Never park a delivered crate across a route you still need. Before a final push, trace the paths your remaining crates will take. If the crate you are about to finish sits on the only route for another one, do that other one first.
- Move crates out of doorways early. A crate sitting in a narrow gap will be in your way for the whole level. Deal with it before it becomes urgent, when you still have room to choose which side you push from.
- Keep one crate as your flexible one. If several crates could serve several targets, commit the constrained ones and leave the crate with the most freedom unassigned. It absorbs your planning mistakes.
The habit that ties all of it together is a two-second check before each push. Where does this crate land? Is that square a corner, or a wall with no target on it? Will it touch another crate? And after the push, can I still walk to the side of it that I will need next? Four questions, most of them answerable at a glance, and together they prevent nearly every unrecoverable position.
Numbers we wrote down while testing our own levels, all of them estimates and none of them records: an introductory level with three or four crates takes us about one to three minutes, and a mid-sized level with six to eight crates runs anywhere from five to twenty minutes including the restarts. We restart roughly one level in three on a first attempt, which drops sharply once the four deadlock patterns are familiar. Unlike a move count, none of this is arithmetic — it is what a stopwatch showed a few people on a few evenings.
When a level beats you
Restarting is not a failure in Sokoban; it is a normal part of solving one. A first attempt is reconnaissance — you learn where the corners are, which corridors are one wide and which target is the awkward one. The second attempt is the real solve, and it usually goes faster than the first attempt's opening ten moves did.
If a level defeats you twice, stop pushing and count. How many crates, how many targets, and which targets have only one possible entry direction? Write those pairings down if you have to. Sokoban levels are hand-built, and the difficulty is nearly always concentrated in one pairing the designer expected you to get wrong.
Where the puzzle came from
Sokoban was created by Hiroyuki Imabayashi and published by the Japanese software company Thinking Rabbit in 1982. The name is Japanese for warehouse keeper, which is a fair description of the job: you are a person in a storeroom, pushing crates onto marked floor squares, with no ability to lift or pull anything.
The design has been copied and extended for four decades, and it has also attracted serious attention from computer scientists, because deciding whether a given level can be solved is a genuinely hard computational problem rather than a matter of searching a little longer. That is an unusual thing to be able to say about a puzzle with three rules.
Our own version of the puzzle lives at Crate Push. It is written here, with our own levels; Sokoban is the name of the 1982 original and of the genre it created, and we mention it because that is the vocabulary players use, not because the name belongs to us.
Questions players ask
Why can a level become unsolvable without any warning?
Because crates can only be pushed, never pulled. One push can put a crate on a square it can never leave, and the game has no way to tell you that the level ended.
Which deadlocks should I learn first?
The corner, the wall with no target on it, the two-by-two block of crates, and the one-wide corridor entered from the wrong side. Those four cover most lost levels.
What does solving backwards mean?
Starting at a target and asking where the crate came from and where you stood to push it, then repeating until you reach a crate's starting square. In reverse you are pulling, and pulling has no deadlocks.
Does it matter which crate I deliver first?
Frequently it decides everything. Fill enclosed targets first and leave the ones in open floor for last, because a delivered crate is an obstacle you cannot move again.
Is walking ever a mistake?
Walking never changes the board, but it changes which side of a crate you can push from. In a one-wide corridor that is the whole game.