This is an interactive HTML version of the tile sliding puzzle. Click on a tile adjacent to the open space to move it.
The auto-solver uses Dijkstra's A* heuristic search to find the optimal sequence of moves to the solved state.
Key Findings & Optimizations
- Heuristic: Manhattan distance combined with linear conflict works substantially better than simple Manhattan distance alone.
- Asynchronous search loop: The search explores thousands of nodes. To avoid freezing the browser, the loop is unrolled and made asynchronous with
setTimeout().
- Remaining distance weighting: Standard A* balances moves already taken and estimated remaining distance equally (1:1), causing an exponential node explosion on a 15-puzzle. Weighting remaining distance 3× to 4× more heavily than moves taken makes closing distance to the goal reward the search path, guiding the solver directly to the solution and preventing browser hangs.
- State representation: A compact 16-character string representation for the state yields far better performance in JavaScript than 2-D numeric arrays when checking against the “closed” set.
- Precomputed adjacency: Tile neighbor adjacencies are precomputed into a static lookup table, avoiding neighbor search overhead at runtime.
AI was used (via cecli) to restyle, and refactor the application, after it was built.