Developer Port C++ Sokoban Solver to Browser Using A* Algorithm
The JavaScript-based engine solves standard levels in milliseconds, while the most complex board relies on offline parallel computing to bypass browser memory constraints.
Menachem Kornreich has released a browser-based Sokoban puzzle solver, offering a plain JavaScript implementation of a native C++ engine. The tool is designed to find provably optimal solutions, identifying the fewest moves required to complete each level rather than simply providing a valid path.
Sokoban, a grid-based puzzle originating in the 1980s, requires players to push boxes onto goal squares. In the variant addressed by this solver, the warehouse keeper must also finish on a goal square. The puzzle is fundamentally an A* search problem, though a naive approach exploring individual keeper steps can become computationally inefficient on crowded boards.
The released tool successfully solves levels one through 14 live within the browser, returning the optimal solution in milliseconds. The move counts displayed as optimal on the interface correspond directly to the results generated by this client-side solver, confirming the accuracy of the JavaScript port.
Level 15, an eight-box maze, presents a significant exception due to its computational intensity. The optimal search for this board requires exploring approximately 49 million states and demands more than 1 GB of memory, making live execution in a browser tab impractical.
To address this constraint, the optimal solution for level 15, consisting of 184 moves, was computed offline. The native C++ build utilised a parallel A* search across 24 cores, completing the calculation in approximately five seconds. This result was verified by replay and is now precomputed on the page, meaning the solver simply plays back the hardcoded solution for this specific level.
The project highlights the technical trade-offs between client-side execution and server-side or offline processing when dealing with high-memory search algorithms. By porting the engine to JavaScript, Kornreich provides a transparent view of the solver’s performance on standard levels while acknowledging the hardware limits of web environments for more complex scenarios.
