📦 Play it (Reset + 3 levels + a "is it still solvable?" button): https://dev48v.infy.uk/game/day23-sokoban.html
Sokoban looks like the simplest puzzle in the world. A little worker in a warehouse, some crates, some marked spots on the floor. Push every crate onto a marked spot and you win. That's it. And yet Sokoban is genuinely hard — hard enough that deciding whether a level is solvable at all is PSPACE-complete, the same difficulty class as some seriously nasty problems. What makes it so brutal is one tiny design choice: there is no undo inside the rules. You can push a box, but you can never pull one back. Get that into your head and everything about the game — and the code — falls out of it.
The whole game is a grid of characters
The first thing I like about Sokoban is that the level format is ancient and beautiful: it's just text. One line per row, one character per tile. # is a wall, a space is open floor, . is a goal, $ is a box, @ is the worker. So a level is literally an array of strings, and reading any tile is grid[r][c]. That single data structure holds the entire state of the puzzle. No sprites, no physics engine — a spreadsheet of letters.
The one subtlety is that a box can sit on a goal. A tile is sometimes "goal AND box" at the same moment. Trying to cram that into a single character gets ugly fast, so I split the world into two layers: a static floor layer that only remembers walls and goals, and separate live collections for the boxes and the worker. Rendering draws the floor first, then paints the movers on top. A box parked on its goal just shows as a box — with the goal quietly still underneath, never lost.
Every move is a delta
All movement is one step in one of four directions, so each arrow key becomes a (dr, dc) delta. Up is (-1, 0) — and yes, up subtracts from the row, because rows grow downward. That off-by-one convention is the single most common bug in grid games, so I got it out of the way early. Both the keyboard and the on-screen D-pad funnel through one move(dr, dc) function, which means the rules live in exactly one place and can't drift apart between directions.
The rule that makes Sokoban Sokoban
Here's the heart of it. When the worker tries to move, look at the tile directly ahead:
- If it's a wall, do nothing.
- If it's floor, just step onto it.
- If it's a box, look one more cell in the same direction — the tile beyond the box. Only if that tile is empty floor (not a wall, not another box) can you push. Then the box slides forward and the worker steps into the space it left.
That's two look-aheads, and it encodes both classic Sokoban restrictions at once: you can't push a box into a wall, and you can't push two boxes at the same time. One push touches two tiles and needs three positions — worker, box, and the cell beyond — all lined up.
Winning is almost anticlimactic after that. Since goals never move, I just check whether every goal position also holds a box. A well-formed level always has as many boxes as goals, so "every goal covered" and "every box home" are the same statement. I run it after each move, and the same count powers the "boxes home 2/3" readout.
Where it gets evil: deadlocks
Because there's no pull, some mistakes are permanent. Push a box into a corner where two walls meet and it's stuck forever — you can't push it in any direction from a corner. Unless that corner is a goal, the level is now impossible even though nothing looks over. A box pinned flat against a wall with no goal along that wall is another dead state. Good players learn to see these before committing a push; real solvers actively prune them.
The "is it still solvable?" button
To answer that, I treat the puzzle as a graph. A state is a snapshot: where the worker is plus where all the boxes are. From one state the four moves lead to up to four neighbours, and the goal is any snapshot with every box on a goal. A breadth-first search fans outward from the current position, remembering every state it has seen so it never loops, until it either reaches a solved state or runs out of new ones. The number of states explodes fast, so I cap the search and dedupe aggressively.
Swap BFS for A* — same idea, but guided by an estimate like the total distance from each box to its nearest goal — and you've got the skeleton of a real Sokoban solver. Not bad for a game that's just a grid of letters and a rule about looking one cell ahead.
Part of GameFromZero. 🌐 https://dev48v.infy.uk
Top comments (0)