Technical Guide to the Sokoban AI Solver

Practical Summary

The Sokoban AI solver is a specialized tool designed to find the provably optimal solution for Sokoban puzzles, where the objective is to push every box onto a goal while ensuring the warehouse keeper also finishes on a goal. By utilizing a move-optimal macro-push A* algorithm, the solver calculates the minimum number of keeper moves required to reach a winning state. It is particularly effective for users who require mathematically verified optimal solutions rather than heuristic-based approximations. The solver operates by treating the puzzle as a search problem, where each edge represents a complete box push rather than individual walking steps, significantly reducing the search space complexity.

Prerequisites and Core Mechanics

To utilize the solver effectively, users must understand the fundamental rules of Sokoban as defined in the Sokoban documentation. The warehouse is a grid where the keeper moves one square at a time. A box can only be pushed if the square immediately behind it is empty or a goal. The solver requires a board configuration where the number of goals is exactly one greater than the number of boxes, accounting for the keeper's final position. The tool is implemented as a plain-JavaScript port of a native C++ solver, meaning it is designed to run within a browser environment while maintaining high computational efficiency through memory-conscious data structures.

The Macro-Push A* Algorithm

The core of the solver is a move-optimal macro-push A* search. Unlike naive implementations that explore one keeper step at a time, this approach defines each search edge as a complete box push. The cost of each edge is calculated as the keeper's shortest walk to the push position plus one. This method allows the search to skip over individual walking steps, focusing entirely on the sequence of pushes. By using an admissible heuristic, the solver ensures that the returned solution is the true minimum number of keeper moves. This algorithmic choice is critical for performance, as it prevents the state space from exploding on crowded boards.

State Representation and Memory Management

Efficiency is achieved through compact bitmask states. The solver packs box positions into a 32-bit integer based on the board's reachable live cells, while the keeper's position is stored in a separate number. This results in a state representation that occupies approximately 8 bytes, allowing millions of states to fit within tens of megabytes of memory. The solver utilizes a dial bucket queue for the A* frontier and an open-addressed hash table for the visited set, which includes parent links for path reconstruction. This design is allocation-free and cache-friendly, which is essential for maintaining performance during intensive search operations.

Deadlock Pruning and Heuristics

To further optimize the search, the solver employs deadlock pruning techniques. A static dead-square table is generated using reverse-reachability from the goal positions. Combined with a freeze check, this allows the solver to discard provably unsolvable positions early in the search process. A wall-aware push-distance lower bound is used to keep the A* heuristic admissible, ensuring that the solver remains optimal. These mechanisms allow the tool to solve most standard boards in milliseconds, as the search space is pruned of branches that cannot lead to a valid, optimal solution.

Limitations and Offline Computation

While the solver is highly efficient, it faces limitations with extremely complex boards. For instance, the 8-box maze (Board 15) requires exploring approximately 49 million states and exceeds 1 GB of memory, making it impractical for browser-based execution. In such cases, the optimal solution is computed offline using the native C++ version of the algorithm, which utilizes parallel A* search across multiple cores. The browser-based tool then plays back the precomputed solution. Users should be aware that for exceptionally large or dense puzzles, the browser-based solver may not be able to complete the search within standard memory and time constraints.

Workflow and Usage

The documented workflow involves loading a board configuration and initiating the solver. The interface provides controls for resetting the board, undoing moves, and adjusting the AI speed. The solver automatically processes the board to find the optimal move sequence. Users can observe the move count, which is compared against known optimal values for standard boards. Because the solver is designed for optimality, it is best suited for puzzle enthusiasts, researchers, or developers interested in pathfinding algorithms and state-space search optimization. It is not intended for casual play where only a valid, non-optimal solution is required.

Technical Implementation Details

The solver's architecture is built to minimize overhead. By avoiding large object allocations and utilizing typed arrays for the hash table, the implementation remains stable even during deep searches. The following logic describes the core search edge cost calculation:

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.

This approach ensures that the search remains focused on the critical decisions of box placement, effectively abstracting the movement of the keeper into the cost of the push itself.