How Slider finds a route

1. A puzzle is a maze of positions

Every arrangement of the tiles is a position. A move turns one position into a neighbouring one. Solving the puzzle therefore means finding a path from the position you have to the solved one, through a maze whose corridors are moves. Computer scientists call such a maze a graph, and finding a path through it a search.

The difficulty is the size of the maze. Only half of the possible arrangements can be reached (the next section explains why), so a board with n cells has n! ÷ 2 positions:

A 3 × 3 board is trivial for a computer. A 4 × 4 is out of reach for brute force, and the larger boards are hopeless without being clever, which is the whole subject of this page.

2. Can it be solved at all?

Exactly half of all arrangements can never reach the solved position. There is a neat test. Read the tiles in order, ignoring the gap, and count the inversions: pairs where a larger number comes before a smaller one. On a board that is an odd number of cells wide, such as 3 × 3, a position is solvable exactly when its inversion count is even.

The reason is that every move preserves that parity. Sliding a tile sideways does not change the reading order at all. Sliding one up or down makes it hop over two others on a 3 × 3 board, which changes the count by an even number. The solved board has no inversions, so it can only ever reach even ones. On boards with an even width the gap’s row has to be included in the sum, but the idea is the same. It was worked out in 1879, when the 15 puzzle was a craze.^[1]

Try it. Swapping two tiles changes the inversion count by an odd number, which is why the board below becomes impossible.

Slider checks this before it searches. Without the check, an impossible 3 × 3 board would send the search through all 181,440 reachable positions before it could admit defeat.

3. Searching blindly

The simplest search is breadth-first. Try every move from the start. Then try every move from each of those positions, then from theirs, and so on, widening one step at a time. The first time the solved position turns up, you have found a shortest route, because every shorter one has already been tried.

It is guaranteed, and it is hopelessly wasteful. It has no idea where the goal is, so it explores in every direction equally. On the hardest 3 × 3 position, which needs 31 moves, it looks at 181,438 of the 181,440 possible positions. The comparison table further down shows this for yourself, and the grid in section 5 shows it as a picture: set the weight to 0 and watch the search spread out like a ripple.

4. Guessing how far is left

The cure is to give the search some sense of direction. A heuristic, written h, is a cheap estimate of how many moves a position still needs. Three are used in this project, each smarter than the last:

1. Misplaced tiles. Count the tiles that are not in their home cell. Each needs at least one move.
2. Manhattan distance. For each tile, count the squares between it and home, moving only along rows and columns (as a taxi would in a city grid), and add them up. Each move shifts one tile by one square, so this cannot fall by more than 1 per move.
3. Linear conflicts. If two tiles both belong in the row they are currently in, but are the wrong way round, they must pass each other. That is impossible within the row, so one has to step out and back in, costing at least two extra moves that Manhattan distance did not count. The same goes for columns.^[2]

All three share a vital property: they are admissible, meaning they never overestimate. A heuristic that sometimes claimed “10 moves” for a position that really needs 8 could lead a search to throw away the best route. The tests in this repository check that none of the three ever overestimates, on every one of the 181,440 positions of the 3 × 3 board.

Slide tiles below and watch the numbers. The small figure on each tile is its Manhattan distance. Use the button to load a board with two linear conflicts, which are outlined.

5. A*: try the most promising position first

A* uses the heuristic to decide what to look at next. It keeps a frontier of positions it has seen but not yet explored, and gives each one a score:

f = g + h

where g is how many moves it took to get there, which is known exactly, and h is the heuristic’s guess at the moves still to come. So f is the estimated length of the best route through that position. Each step, A* takes the frontier position with the lowest f. If it is the goal, it stops. Otherwise it expands it: it adds its neighbours to the frontier and moves on.

Why is the answer shortest? Because h never overestimates, the score of any position is at most the length of the best route through it. When the goal comes to the front of the queue, every other position on the frontier has a score at least as high, so none of them can lead to a shorter route.^[3]

The puzzle’s positions are hard to draw, so here is the same algorithm on a grid, where positions are squares and moves are steps. The heuristic is the number of steps to the goal if there were no walls. Draw walls by dragging across the grid, drag S and G to move the start and goal, and press Run. Pale squares are the frontier; tinted squares have been expanded.

Things to try:

• At w = 0 the goal is ignored and the search ripples outwards in all directions. That is breadth-first search.
• At w = 1 you get A*: the search leans towards the goal but still finds a shortest route. It expands far fewer squares.
• Put a wall between the start and goal, and see A* walk up to it and then fan out along it until it finds the gap.
• When two squares have the same score, the one nearer the goal goes first. That small rule makes a noticeable difference.

6. A* on the puzzle

On the puzzle, A* scores positions in exactly the same way. Below, the boxes show every position you could move to next, with the score A* would give each. Slide tiles by clicking either the board or a box.

Notice that each move changes g by +1 and the Manhattan part of h by ±1, so f either stays level or rises by 2 (linear conflicts can add a little more). Moving a tile towards home keeps f level; moving it away raises f. A route whose f never rises is a shortest one, and A* is effectively hunting for it.

The highlighted move has the lowest f of the options shown. (Sliding the last tile back is marked as going back and is never highlighted, because A* does not return to the position it came from.) A* would try the highlighted move first, but it also remembers every other position it has seen, and if the new ones turn out to be worse it goes back to an older one. Try always following the highlight and you will find it can wander. A* avoids that by choosing the best position anywhere on its frontier, not just among the latest moves. That memory is what makes it both exact and hungry for memory.

7. Quick: weighted A*

Weighted A* makes one change. It scores positions by

f = g + w × h

with a weight w above 1. The guess now counts for more than the distance already travelled, so the search dives towards the goal rather than exploring evenly. The weight is the slider in the grid above. As it rises, the search expands fewer squares and the route gets a little longer, as Compare all weights shows.

There is a guarantee: if h is admissible, the route found is never more than w times the shortest.^[4] Real routes are usually much closer. In a sample of six random 4 × 4 boards from this project, with w = 3, routes came out 36 to 51 per cent longer than the shortest, against a ceiling of 200 per cent.

Slider’s Quick mode picks w from the board size: 2 for a 3 × 3, 3 for a 4 × 4, 4 for a 5 × 5 and 6 for a 6 × 6. If a pass looks at 1.2 million positions without finding the goal, it gives up and starts again with the weight doubled. That is why it reliably solves boards up to 6 × 6, and why it is not offered beyond that: it remembers every position it has seen, which makes it slow on a 7 × 7 board and liable to exhaust the memory of a browser tab on an 8 × 8.

8. Shortest: IDA*

Plain A* has a weakness. It remembers every position it has seen, and on a hard 4 × 4 that can run to billions. Iterative-deepening A* (IDA*) keeps A*’s scoring but throws away its memory.^[5] It works in passes:

1. Set a limit equal to the heuristic’s estimate for the starting position, which is a lower bound on the answer.
2. Search depth-first, following one route at a time and backing up when a position’s score f exceeds the limit. Remember the smallest score that went over.
3. If the goal was reached, stop: the route is shortest. Otherwise raise the limit to that smallest score and go round again.

Each pass repeats the work of the last, but each also visits several times more positions than the one before, so the final pass dominates and the repetition costs little. The prize is that it only ever holds the current route in memory, which is a few dozen positions rather than billions. The table at the end of the next section shows the passes for a real board.

Slider’s version adds two refinements. It never undoes the move it has just made, and it recalculates the linear-conflict score only for the one row and the two columns (or the reverse) that a move disturbs, instead of for the whole board.

9. All the strategies side by side

Here every strategy in this page solves the same 3 × 3 board. The key number is how many positions each had to expand. The bars use a logarithmic scale, because the differences are enormous.

What to notice. Each better estimate cuts the work dramatically, and on the hardest board linear conflicts expand roughly 37 times fewer positions than breadth-first search. The weighted rows expand a tiny fraction as many, but may return a longer route. IDA* expands slightly more positions than A* with the same heuristic, because it revisits some, but it needs almost no memory to do so. Counts for IDA* are positions visited across all of its passes.

10. Where it stops, and what comes next

Shortest is only offered up to 4 × 4, because a hard 5 × 5 takes far too long with these heuristics. Quick stops at 6 × 6 for the memory reason above. Real solvers do much better, and the ideas are worth knowing:

• Pattern databases. Solve a simplified puzzle, in which only a handful of the tiles matter, once and for every position, and store the exact distances. The result is a far sharper heuristic than Manhattan distance. Combined with IDA*, it cut the search on 15 puzzles more than a thousandfold.^[6] Using several databases that do not share tiles, and adding their answers, extended this to optimal solutions of random 24 puzzles.^[7]
• Layer by layer and fringe. People solve large boards a row or a column at a time, never disturbing what is already home. A program can do the same and finish any size in a flash, but the route is long, about twice the shortest on a 4 × 4. Solving it by hand teaches both methods, with a trainer you can step through.
• Searching from both ends. Start one search from the puzzle and another from the solved board, and stop when they meet.

The 15 puzzle’s hardest positions need 80 moves, which is the true diameter of its maze. For the 3 × 3 it is 31, and the Hardest board button above loads one such position.

11. Reading the code and further reading

The algorithms on this page are all in the repository, and each file is short enough to read in one sitting:

• solver.js: the solvability test, the heuristics, IDA* (solveOptimal) and weighted A* (weightedAStar).
• gridsearch.js: the grid version above, written to be run one step at a time.
• test.js: the tests, which check every claim here that can be checked. They compare the solvers with exhaustive breadth-first search, and confirm that no heuristic ever overestimates.

References

1. Wm. Woolsey Johnson and William E. Story, ‘Notes on the “15” Puzzle’, American Journal of Mathematics, 2.4 (1879), 397–404.
2. Othar Hansson, Andrew Mayer, and Moti Yung, ‘Criticizing Solutions to Relaxed Models Yields Powerful Admissible Heuristics’, Information Sciences, 63.3 (1992), 207–227.
3. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael, ‘A Formal Basis for the Heuristic Determination of Minimum Cost Paths’, IEEE Transactions on Systems Science and Cybernetics, 4.2 (1968), 100–107.
4. Ira Pohl, ‘Heuristic Search Viewed as Path Finding in a Graph’, Artificial Intelligence, 1.3–4 (1970), 193–204.
5. Richard E. Korf, ‘Depth-First Iterative-Deepening: An Optimal Admissible Tree Search’, Artificial Intelligence, 27.1 (1985), 97–109.
6. Joseph C. Culberson and Jonathan Schaeffer, ‘Pattern Databases’, Computational Intelligence, 14.3 (1998), 318–334.
7. Richard E. Korf and Ariel Felner, ‘Disjoint Pattern Database Heuristics’, Artificial Intelligence, 134.1–2 (2002), 9–22.