// HACKER NEWS — CYBERSECURITY
Show HN: Sokoban AI Solver
Sokoban ("warehouse keeper") is a 1980s puzzle: push every box onto a goal. In this variant
the keeper must also finish on a goal.
The warehouse is a grid. On each step the keeper moves one square up, down, left or right.
The keeper cannot walk into a wall or a box. It can push a single box if the
square just beyond the box (in the push direction) is empty floor or a goal. Only one box
moves per step, and a box can be pushed out of a goal again to make room.
Sokoban is an A* search problem, but a naive version that explores one keeper step at a
time explodes on crowded boards. What runs here is a
plain-JavaScript port of a native C++ optimal solver I wrote. It returns the
provably fewest-moves
solution, not just some solution:
Boards 1–14 are solved live to the proven optimum in milliseconds (the move
counts shown as "Optimal" above are exactly what this solver returns). Board 15. The 8-box
maze. Is the exception: its optimal search explores
~49 million states and needs >1 GB, which would take far too long to
run inside a browser tab. So its optimum (184 moves) was computed
offline by the native C++ build of this exact algorithm (a parallel A* search,
~5 s across 24 cores) and verified by replay, and the page simply
plays that precomputed solution back. That is why board 15's answer is hardcoded
rather than searched here.
Built from
my Sokoban solver.
About Sokoban →