Sokoban (“warehouse keeper”) is a 1980s puzzle: push every box onto a goal. In this variant
the keeper mustalsofinish on a goal.
The warehouse is a grid. On each step the keeper moves one square up, down, left or right.
The keepercannotwalk into a wall or a box. Itcan push a single boxif 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 pushedoutof 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 aplain-JavaScript port of a native C++ optimal solverI wrote. It returns theprovably fewest-movessolution, not just some solution:
Boards 1–14 are solved live to theproven optimumin 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 computedofflineby the native C++ build of this exact algorithm (a parallel A* search,
~5 s across 24 cores) and verified by replay, and the page simplyplays that precomputed solution back. That is why board 15’s answer is hardcoded
rather than searched here.
Built frommy Sokoban solver.About Sokoban →