Sokoban

Getting into Sokoban Properly

Sokoban is a puzzle genre where you push boxes onto designated target spots on a grid. The rules are brutally simple. You can move up, down, left, right. You can push a box, but you cannot pull it. If you push a box into a corner or against a wall where it can't be moved again, that box is stuck and the puzzle is either unsolvable or requires rewinding many moves. The Japanese term literally translates to "warehouse man." The first commercially released version appeared in 1982, and the genre has been a staple of algorithmic puzzle design ever since. The basic engine in any Sokoban clone is straightforward. Load a map file. Parse walls, empty floor, boxes, targets, and the player starting position. Process input. On each keypress, calculate whether the adjacent tile is walkable and whether pushing a box would land it on a target or valid floor space. Render the state. That's the entire runtime loop. Most implementations are under two hundred lines of code.

The Sokoban Ecosystem and Where to Start

If you want to play, sokoban.online is the cleanest browser-based client with proper undo, level navigation, and speedrun tracking. For a downloadable experience, XP Sokoban on Windows remains one of the most complete packages available, bundling all the standard level sets. The classic benchmark is the 40-World Sokoban set from the 1987 competition, which most implementations ship with. For deeper study, the World Championship-level sets by Ulf Andersson and the 110x110 maps from the 2000s push even experienced players into serious manual solving territory. When I started writing solvers for this, I quickly learned that a naive depth-first search is useless past about eight boxes. The branching factor explodes because every push creates new states, and unlike chess where you alternate turns, Sokoban gives you four movement options per turn plus potential pushes, and you can shuffle around the player endlessly without changing the puzzle state. This means any practical solver needs to avoid exploring the same positional state twice. The standard approach is bidirectional search combined with deadlock detection. You run A* from the start state and from the goal state simultaneously, meeting in the middle. The heuristic needs to account for something beyond simple Manhattan distance because pushing one box often forces another box out of the way. I ended up using the relaxed version where you ignore box-box blocking, but I also added a static deadlock table that precomputes every wall-adjacent and corner-adjacent cell as an invalid final position for any box. This cut my solver runtime on median 40-world levels from about 45 seconds down to roughly three seconds on a standard laptop.

The counter-intuitive part most beginners miss is that the hard Sokoban puzzles are rarely hard because they require many moves. They are hard because the solution path is extremely narrow and any wrong push immediately creates an unrecoverable deadlock. I spent weeks on a single 14-box level where the correct first push was not obvious from reading the map, and once you make the wrong choice, you have to undo over sixty moves to get back. This is why manual solvers always scan for forced sequences before committing. If a box is between the player and a wall with no alternative path around it, you already know you have to push it away from that wall first, or you will trap it. Another practical detail people overlook is that Sokoban levels can contain removable walls in some variants, and the standard level format does not always distinguish between a wall that is destructible and one that is permanent. When parsing custom .sok files, I always check whether the level creator included a separate destructible-wall layer because mixing them up breaks the rendering entirely. The standard format uses numeric codes where 1 is a wall, 2 is a floor, 3 is a target, 4 is a box on target, 5 is the player, and 6 is a box on a target. Some newer formats use Unicode characters instead, and a parser that only handles the numeric version will silently corrupt the map. If you are building your own implementation, the hardest part is not the game loop. It is getting the undo system right. Each move needs to store the previous player position, the box positions affected, and the targets state. If you do not store the full board snapshot at each step, an undo operation will sometimes restore the boxes to the wrong coordinates after a multi-box push sequence. I lost a full day to this on my first attempt.

For level generation, the common mistake is creating levels that look random but are actually unsolvable. A proper generator starts from a solved state and works backward by reversing pushes into pulls, ensuring every intermediate state remains reachable. Randomly placing boxes on a random maze produces an unsolvable configuration roughly eighty percent of the time, which makes it useless for anything other than a novelty test. The Sokoban community is small but persistent. The annual World Championships still draw competitors who solve levels in under a minute by memorizing common patterns. If you want to improve quickly, stop treating each level as a fresh problem and start recognizing the structural motifs. Corner traps, tunnel squeezes, and rotation puzzles appear repeatedly across different maps. Once you internalize those patterns, manual solving becomes a matter of pattern matching rather than brute calculation.