Sokoban Solver Screensaver
Sokoban Solver is a free screensaver that solves ten small Sokoban puzzles with an A* search, running the search live and then replaying the solution move by move. It shows each level's real search statistics: states expanded and generated, pushes and moves. Press ESC to exit.
Live preview
Press ESC to leave fullscreen. Settings are saved in your browser only.
How the Sokoban Solver screensaver works
In Sokoban you push boxes onto goal squares; you can push one box at a time and never pull. The solver searches over pushes, not steps: a state is the set of box positions plus the region the pusher can currently walk to, and every legal push of every reachable box is one move to a new state. Walking between pushes is free in the search, so the search cost counts pushes.
The search is A*. The estimate for a state is the sum, over its boxes, of the fewest pushes that box would need to reach any goal if nothing else were in the way, calculated once per level by searching backwards from the goals. That never overestimates, so the first solution A* finds has the minimum number of pushes. Two kinds of deadlock are pruned: squares from which a box can never reach a goal, and frozen boxes that can never move again, such as a 2 × 2 block of boxes off the goals.
The search runs in slices of about three milliseconds per frame so the page stays smooth. While it works, dashed outlines show the box layout of the state it expanded last, and the panel counts states expanded, states generated, the frontier size and the current lower bound. When it succeeds, the solver builds the full move list, adding the walking between pushes, and the saver replays it with sliding crates. The level number, moves and pushes update as it goes.
The ten levels are original small puzzles: six were written by hand and four were made by playing random pulls backwards from a solved position, then kept only if the solver proved them solvable and they were not trivial. Each level was solved offline in Node and its solution replayed through a separate rules simulator before shipping.
About Sokoban
Sokoban (Japanese for warehouse keeper) was created by Hiroyuki Imabayashi, with Thinking Rabbit publishing the first commercial version in Japan in 1982. It has become a standard test problem in artificial intelligence research.
Solving general Sokoban is PSPACE-complete (Culberson, 1997), and the hardest published puzzles need specialised solvers with much stronger deadlock detection than the simple frozen-box and dead-square rules used here.
The solver's push counts for the first six levels were cross-checked against an independent breadth-first search, and pruning was checked by solving every level with and without the frozen-box rule and comparing push counts. These are the checks the author ran; the solver is not claimed to be state of the art.
A worked example
Level 6, "Squeeze", has three crates: the solver expands 168 states, generates 225, and finds a 16-push solution that takes 40 moves including walking. An independent breadth-first search over the same rules also found 16 pushes as the minimum. The hardest level, "Long haul", took 12,687 expansions to find a 20-push, 74-move solution.
Settings & tips
- Replay speed sets how many moves per second the solved puzzle is played back at; the search itself always runs at full speed.
- Accent colours the crates, goal rings and the dashed search outlines.
- The solution has the fewest pushes, not necessarily the fewest total moves, because walking is free in the search.
- Press ESC to leave fullscreen.
Frequently asked questions
- Is the solver really running, or is this an animation?
- It really runs. Each level is solved when it comes up, in the page, and the counts shown are from that run. Only the replay of the finished solution is an animation.
- Are the solutions the shortest possible?
- They have the minimum number of pushes, because the heuristic never overestimates. They are not guaranteed to have the fewest total moves, since the search does not count walking.
- Why are the search times so short?
- The levels are small. The hardest takes about twelve thousand expansions, which a modern browser does in a fraction of a second. Large published Sokoban puzzles are far harder and need much stronger solvers.
- What counts as a deadlock?
- A box on a square from which it can never reach a goal, or a box that can never move again, and is not on a goal. States containing either are discarded because they cannot lead to a solution.
- Are these levels from a published pack?
- No. They are original puzzles written for this saver, so no level pack is copied.
- What if a level had no solution?
- The search would run out of states and the saver would show "no solution" and move on. All ten shipped levels were checked solvable beforehand.
- How hard is Sokoban in general?
- Solving Sokoban is PSPACE-complete, as shown by Joseph Culberson in 1997, so no efficient general method is known. These puzzles are far smaller than the cases that result is about.