How the Sliding Puzzle Solver Works: IDA* Search Explained
Scramble the sliding puzzle solver and it plays the tiles back into order in front of you — and for the 8-puzzle, it does so in the fewest moves that exist. The engine is IDA* (iterative-deepening A*), steered by a heuristic that estimates how far a board is from solved. We ran its exact code headless: over 200 random 8-puzzles it found the provably shortest solution every time — averaging 21.6 moves while exploring only about 1,500 positions in a couple of milliseconds.
The Heuristic: How Far From Solved?
A* needs a fast, never-overestimating guess of the moves remaining. The solver uses the classic Manhattan distance — for every tile, how many rows plus columns it sits from its home square — and strengthens it with linear conflict: when two tiles are already in their correct row or column but reversed, one must move aside and back, so at least two extra moves are added. A sharper heuristic means the search prunes harder and reaches the answer faster, without ever overshooting the true shortest distance.
IDA*: A* Without the Memory Bill
Ordinary A* keeps every frontier position in memory, which balloons on hard puzzles. IDA* avoids that: it runs a depth-first search with a cost ceiling equal to the heuristic, and if nothing is found it raises the ceiling to the smallest cost that exceeded it and searches again. Each pass uses almost no memory, and because the heuristic never overestimates, the first solution it finds at a given ceiling is guaranteed to be the shortest — that is what makes the 8-puzzle result optimal.
Measured: Optimal and Instant
We generated random solvable scrambles and solved them with the shipped engine, recording the solution length and the number of positions expanded:
| Puzzle | State space | Avg moves | Hardest seen | Avg nodes | Avg time |
|---|---|---|---|---|---|
| 8-puzzle (3×3) — optimal | 181,440 | 21.6 | 28 | 1,510 | 2 ms |
| 15-puzzle (4×4) — near-optimal | ~10¹³ | 57.6 | 89 | 204,134 | ~1 s |
8-puzzle: 200 random solvable boards, IDA* with weight 1 (guaranteed shortest). 15-puzzle: 100 boards with the shipped lightly-weighted search. The 8-puzzle's whole state space is only 181,440 positions; the 15-puzzle's is about ten trillion, which is why guaranteed-optimal search moves to near-optimal there.
A headless scramble-depth sweep — where the 8-puzzle's optimal solution length converges to ~22 moves (matching the known ~21.97 average) and the 15-puzzle averages ~53 moves — is published as the LK Forge Sliding Puzzle Solver Benchmark dataset on Hugging Face.
Why not always optimal? The 8-puzzle's longest possible shortest solution — its "God's number" — is 31 moves, and the whole graph fits in memory, so optimal search is trivial. The 15-puzzle's God's number is 80 and its graph is ten trillion positions; searching for the guaranteed shortest solution can take far too long for a browser tab. The solver trades a handful of extra moves for an answer that always arrives in about a second.
Half of all scrambles are impossible. Slide tiles around and you can only ever reach half of their arrangements — the other half have the wrong parity and can never be solved. The solver checks parity first (counting how many pairs of tiles are out of order), so it instantly rejects an unsolvable board instead of searching forever.
Reproduce It Yourself
The engine is a single DOM-free JavaScript file you can run with Node:
import fs from 'fs'; import vm from 'vm';
// grab the shipped engine: lkforge.com/tools/puzzles/js/sliding-solver-engine.js
const ctx = {}; vm.createContext(ctx);
vm.runInContext(fs.readFileSync('sliding-solver-engine.js','utf8') +
'\nglobalThis.LKSlide = LKSlide;', ctx);
const S = ctx.LKSlide.makeSolver(3); // 8-puzzle
const board = [1,2,3,4,0,6,7,5,8]; // 0 = blank
const r = S.solve(board, 5000000, 1); // weight 1 = optimal
console.log(r.moves.length, 'moves,', r.nodes, 'nodes');Frequently Asked Questions
Is there a sliding puzzle solver?
Yes — this page's sliding puzzle solver is a free in-browser tool for the 8-puzzle and 15-puzzle. Set up or scramble a board and it plays out the solution step by step. No sign-up.
What algorithm does the sliding puzzle solver use?
IDA* — iterative-deepening A* — guided by a Manhattan-distance heuristic strengthened with linear-conflict detection. The 8-puzzle is solved optimally; the far larger 15-puzzle uses a lightly weighted, near-optimal search that is always fast. Not a generative-AI or LLM wrapper.
Does it find the shortest solution?
For the 8-puzzle, yes — over 200 random boards it returned the provably shortest solution every time (avg 21.6 moves, ~1,500 nodes, a couple of milliseconds). The 15-puzzle is too large for guaranteed-optimal search in a browser, so there it returns a near-optimal solution, typically within about 10% of the shortest, in around a second.
Can every scramble be solved?
Only half of all arrangements are reachable — the solver checks the board's parity first, so it never tries to solve an impossible scramble.
Is the sliding puzzle solver free?
Completely free, no account required. It runs client-side in your browser, so nothing you enter is uploaded.