How to use the solver
The tool above solves any solvable 3×3, 4×4 or 5×5 board optimally — the answer it returns is the shortest possible move sequence, not just a working one.
- Press Edit and enter your board: number the tiles as they should read in the finished puzzle (top-left is 1), and place them where they currently sit. Solving a picture puzzle — from a game, a photo app, a wooden toy? Mentally number the finished image top-left to bottom-right first.
- Press Solve. The move list appears instantly for 3×3 boards and within moments for 4×4.
- Play the moves back on your real puzzle, one at a time.
If the solver says the board is unsolvable, that is not a bug — exactly half of all arrangements can never be solved, and no sequence of legal moves will fix them. Prefer to learn the technique instead of reading out moves? The human method is here.
How a sliding puzzle solver works — six algorithms compared
If you are implementing a sliding puzzle solver and are not sure which algorithm to use, the rest of this article compares six well-known ones across speed, memory, code complexity, and the board size they comfortably handle. The answers are different for the 3×3, the 4×4, and the 5×5.
1. Breadth-first search (BFS)
The dumbest correct algorithm. Explore states level by level until you find the goal.
- Time — exponential in solution depth. For the 8 puzzle it terminates in a fraction of a second. For the 15 puzzle, it does not terminate before your computer runs out of RAM.
- Memory — keeps the entire visited set in memory. Tens of millions of states for hard 15 puzzles.
- Code complexity — twenty lines.
- Verdict — fine for the 3×3, useless beyond.
2. A* with Manhattan distance
The first real algorithm. Same structure as BFS but states are popped from a priority queue ordered by f = g + h, where h is the Manhattan distance heuristic.
- Time — milliseconds for the 8 puzzle, seconds to minutes for the 15 puzzle.
- Memory — still keeps everything explored in memory; manageable for 8, painful for 15.
- Code complexity — fifty lines, mostly priority-queue plumbing.
- Verdict — the right tool for the 8 puzzle. Borderline for 15.
3. A* with Manhattan + linear conflict
Add 2 moves to the heuristic for every pair of tiles in the same row that are both in their goal row but in the wrong order (similarly for columns). They will need to pass each other, which Manhattan distance cannot see.
- Time — typically 5–15% faster than plain Manhattan A*.
- Memory — unchanged.
- Code complexity — sixty lines.
- Verdict — strictly better than plain Manhattan A*. Always use it.
4. IDA* with Manhattan + linear conflict
Iterative-deepening A*. Do depth-limited DFS using f-cost as the depth measure, raising the limit each iteration. Trades memory for time by re-exploring.
- Time — slightly slower per node than A* due to repeated exploration, but the lower memory pressure usually wins on hard 15 puzzles.
- Memory — O(depth), not O(states explored). This is the win.
- Code complexity — eighty lines (recursive DFS, threshold management).
- Verdict — the right tool for the 4×4. The standard since Korf 1985.
5. IDA* with walking distance
Walking distance is a tighter heuristic. Precompute, for each tile arrangement projected onto rows only, the minimum number of row-swap operations to put each tile in its correct row. Same for columns. Add.
It captures something Manhattan misses: tiles in the same row "fighting" for the same slot.
- Time — typically 2× faster than Manhattan + linear conflict on hard 15 puzzles, because the heuristic is tighter so IDA* prunes more.
- Memory — adds a small precomputed table (~500 KB for a 4×4).
- Code complexity — 150 lines. The precompute is BFS on a reduced state space.
- Verdict — the right tool for the 4×4 if you have the engineering budget. The first non-trivial improvement.
6. IDA* with additive disjoint pattern databases
The strongest known heuristic for sliding puzzles. Partition the tiles into disjoint groups (a common 15-puzzle partition is 7+8, or 5+5+5). Precompute, for each group, the cost of permuting the group's tiles to their goal positions over all possible arrangements of that group. At search time, look up each group's contribution and sum.
- Time — solves the hardest 15 puzzle in milliseconds. Solves random 24 puzzles in seconds.
- Memory — significant. A 7+8 partition for the 15 puzzle is about 1 GB. A 5+5+5+9 partition for the 24 puzzle is about 4 GB. Memory dominates the engineering.
- Code complexity — 300+ lines. The precompute step uses retrograde BFS over the group state space and is the bulk of the work.
- Verdict — the right tool for 5×5 and 6×6. Overkill for 3×3.
Summary recommendations
If you are writing a solver today:
- For 3×3, use A* with Manhattan + linear conflict. Anything else is over-engineering.
- For 4×4, use IDA* with walking distance. Pattern databases give marginal wins at this size; the engineering complexity isn't worth it.
- For 5×5, use IDA* with additive pattern databases (5+5+5+9 is standard). Without pattern DBs you will time out on the hardest instances.
- For 6×6 (the 35 puzzle), the same algorithms can solve random instances, but the hardest cases are still research questions. Most apps don't try.
What about machine learning?
A reasonable question in 2026. Neural network heuristics have been studied since at least 2014 and can produce fast heuristics for sliding puzzles. The catch is that they are typically not admissible — they can overestimate, which means the resulting algorithm is no longer guaranteed to be optimal. For app developers who want guaranteed-optimal solutions for difficulty calibration, classical pattern databases remain the right tool.
For research interest, pattern databases trained by a neural network produce slight speedups on the hardest 15-puzzle instances. Useful for academic papers, marginal for shipping software.
What goes in a real app
A shipping mobile app that needs a solver for hint generation almost always lands on:
- IDA* + walking distance for the 4×4.
- IDA* + a small pattern DB for the 5×5.
- One next-move-only call from the hint button.
- Everything runs on-device. The whole solver is a few hundred kilobytes of code plus a few megabytes of precomputed tables.
That is the right pragmatic stack for a calm phone app. Slide Puzzle's hint button works exactly this way.