# Show HN: Sokoban AI Solver > Source: > Published: 2026-08-17 13:07:00+00:00 # Sokoban Sokoban ("warehouse keeper") is a 1980s puzzle: push every box onto a goal. In this variant the keeper must *also* finish on a goal. **0** Optimal: **–** ## How to play & the rules 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. - **Controls:** arrow keys or`W A S D` , or the on-screen pad.**Undo** steps back.**Reset** restores the board. - **Goal:** the puzzle is won when*every*movable entity. Every box*and*the keeper. Is sitting on a goal. That is why each board has one more goal than it has boxes: the last goal is for the keeper. - **Objective:** reach that state in as few moves as possible. For several boards the optimal move count is known and shown above. The AI (with an admissible heuristic) returns an optimal solution on the boards it can search exhaustively. ## How the AI solver works 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: - **Move-optimal macro-push A*.**Each search edge is a whole*box push*costed as (the keeper's shortest walk to the push spot) + 1, so the total is the true minimum number of*keeper moves*, while the search skips over the individual walking steps. - **Compact bitmask states.** The boxes are packed into a 32-bit integer over the board's reachable "live" cells and the keeper into one more number, so a whole state is a single ~8-byte key instead of a ~1 KB object. Millions of states fit in tens of MB. - **Dial bucket queue + open-addressed hash.** The A* frontier is a bucket queue keyed by cost, and the visited set (with the solution's parent links) lives in a flat typed-array hash. Allocation-free and cache-friendly. - **Deadlock pruning.** A static*dead-square table*(reverse-reachability from the goals) plus a*freeze*check discard provably-unsolvable positions, guided by a wall-aware push-distance lower bound that keeps A* admissible (hence optimal). 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](https://github.com/mkornreich/sokoban). [About Sokoban →](https://en.wikipedia.org/wiki/Sokoban)