AI tools · 01

Sliding puzzle solver

Set up any position, get the shortest solution

Works for the 3×3 eight-puzzle and the 4×4 fifteen-puzzle. It first checks solvability from the inversion count, then finds the fewest moves with IDA* search. For the rare 4×4 position beyond the search budget it switches to a weighted search and tells you the solution is short but not proven shortest. Everything runs in your browser; nothing is uploaded.

f(n) = g(n) + h(n)h = 0 · inv(σ) = 0 · Solvable –

How it works

What it computes

  1. Can it be solved at all?Exactly half of all arrangements cannot. The parity of the inversion count (pairs where a larger number comes first) decides it, no search needed.n odd: inv(σ) ≡ 0; n even: inv(σ) + r0 ≡ 0 (mod 2)
  2. How far is it?The sum of every tile's row and column distance to its home is a lower bound on the moves left: it never overestimates.h(n) = Σ |xi − x̂i| + |yi − ŷi|
  3. Iterative deepeningFollow only branches whose f stays under the current limit; when none works, raise the limit to the smallest value that exceeded it. Because h never overestimates, the first solution found is a shortest one.f(n) = g(n) + h(n)