Sokoban AI Solver: Optimal Pathfinding in JavaScript

Menachem Kornreich has developed a Sokoban AI solver that finds provably optimal solutions—the absolute minimum number of keeper moves—using a high-performance JavaScript port of a native C++ solver. The tool demonstrates the application of "classic AI" search techniques to solve complex grid-based puzzles efficiently within a browser environment.

Technical Implementation of the Solver

The solver is built on an A* search algorithm, but it avoids the state-space explosion typical of naive implementations by employing several optimization strategies:

Macro-Push A* Search

Instead of treating every individual keeper step as a search edge, the solver uses a macro-push approach. Each edge in the search graph represents a complete box push. The cost of an edge is calculated as the keeper's shortest walk to the push position plus one for the push itself. This allows the search to skip over individual walking steps while still calculating the true minimum number of keeper moves.

State Compression and Memory Management

To fit millions of states into a limited memory footprint, the solver uses compact bitmask states:

• Box Positions: Boxes are packed into a 32-bit integer across the board's reachable "live" cells.
• Keeper Position: The keeper's position is stored as a separate number.
• State Representation: This reduces a state from a ~1 KB object to a single ~8-byte key, allowing millions of states to be fit into tens of megabytes.

Data Structures for Performance

The solver utilizes a dial bucket queue for the A* frontier and an open-addressed hash for the visited set. By using flat typed-arrays, the implementation remains allocation-free and cache-friendly, which is critical for performance in JavaScript.

Deadlock Pruning

To maintain admissibility and ensure optimality, the solver employs two pruning techniques:

• Dead-square table: A static table generated via reverse-reachability from the goals to identify squares where a box cannot be moved to a goal.
• Freeze check: A mechanism to discard provably unsolvable positions based on a wall-aware push-distance lower bound.

Performance and Constraints

While boards 1 through 14 are solved live in milliseconds, the complexity of the 15th board (an 8-box maze) is a significant outlier. The optimal search for this specific board explores approximately 49 million states and requires over 1 GB of memory. Because this would exceed browser tab limits, the solution for board 15 was computed offline using a parallel A* search across 24 cores in C++ and is played back as a precomputed solution.

Community Discussion and Insights

Community members on Hacker News discussed the project as a return to "classic AI" (search and expert systems) versus modern LLM-based AI. Some users pointed out that the solver's approach is a specific variant of the Sokoban puzzle where the keeper must also finish on a goal, adding an extra constraint to the win condition.

Other technical critiques and suggestions were included in the community feedback:

I wonder: maybe the state is overly compressed? Could it speed things up to store (boxes, [every position the keeper can reach without pushing]) rather than (boxes, representative keeper position), so we can reduce recomputation of the keeper walking around?

I wonder: are there any other simple pruning techniques that you could incorporate? Any learnings from state-of-the-art Sokoban solvers, like this one?

Users also noted that the solver allows users to trigger the AI solve from any arbitrary board state, enabling the exploration of "pessimizing" a puzzle by moving boxes into adversarial positions before requesting a solution.