The fifteen puzzle in the fewest moves
A 4 × 4 box holds fifteen tiles numbered 1 to 15, and one cell is empty. A move slides any tile next to the empty cell into it: from above, below, the left or the right. The solved box looks like this: 1 2 3 4 in the first row, 5 6 7 8 in the second, 9 10 11 12 in the third, 13 14 15 and the empty cell in the bottom right corner in the last.
The puzzle was invented in the 1870s by the postmaster Noyes Chapman, and in 1880 it was a craze everywhere. Later Sam Loyd claimed to be its inventor and told of promising a large prize to whoever solved the box with only 14 and 15 swapped. Nobody ever got the prize: back in 1879 William Johnson and William Story proved that exactly half of the arrangements cannot be solved. That position is the second sample.
Find the smallest number of moves that solves the box, or say that it cannot be solved.
Input
Four lines of four numbers: the box row by row from top to bottom; the empty cell is a zero. Each number from 0 to 15 occurs exactly once. If the box can be solved, it takes at most 50 moves.
Output
The smallest number of moves, or -1 if it cannot be solved.
Examples
Example 1
1 2 3 4 5 6 7 8 9 10 0 11 13 14 15 12
2
Example 2
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 0
-1
Limits
- Time · Python
- 10000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 12 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The fifteen puzzle has 16! ≈ 2 · 1013 positions, and breadth-first search, which in its article goes through all positions of the eight puzzle, will not get even to depth 30 here. What hint honestly estimates how many moves are left?
2Hint 2
One move shifts one tile by exactly one cell. Add up, over all tiles, the horizontal and vertical distance from their cells to their places.
3Hint 3
Before searching, check whether the box can be solved at all. Otherwise the search will go through half of twenty trillion positions.
4The idea
This is A* in the space of positions. Vertices are arrangements, edges are moves, each of length 1. The hint is the sum of the Manhattan distances of the tiles to their places. It never overestimates: each move brings at most one tile closer to its place, by at most one cell. It is consistent too: a move changes the sum by exactly one, so the inequality h(u) ≤ 1 + h(v) holds for every move. So the first solved box A* takes from the heap is solved in the fewest moves.
Unsolvable positions are cut off before the search. In the sequence without the empty cell count the inversions, pairs of tiles where the larger stands before the smaller. A horizontal move changes neither the number of inversions nor the row of the empty cell. A vertical move carries one tile past three others: the number of inversions changes by an odd number, and the row of the empty cell by one. So the parity of the sum “inversions plus the row number of the empty cell” never changes. For the solved box it is odd (0 + 3), so positions with an even sum cannot be solved. That all the others can was proved by Johnson and Story.
5Walkthrough
A position is a tuple of 16 numbers (in Go an array, which can be a map key). A dictionary keeps the best known number of moves to each position, the heap triples (g + h, g, position). The hint is not recomputed from scratch: a move changes the distance of just one tile, and the new h comes from the old one in O(1).
Why not a greedy search that always takes the position with the smallest hint? It finds a solution quickly, but a long one: 191 moves instead of 25 on the fourth test, 212 instead of 34 on the seventh. Without the path travelled, g, in the heap key, the search forgets what the way to a position cost it, and there is no guarantee at all. Exactly this proposal, to add the hint to the path travelled, set A* apart from its predecessors in 1968.
The hardest position in the tests is solved in 46 moves. A* with the Manhattan hint takes 262,251 positions from the heap for it and remembers 492,093; a position of 25 moves needs 1041. For positions of 60–80 moves memory will no longer be enough. Two things help then. A stronger hint: for example, “linear conflicts”, two tiles in their own row standing in reverse order, add 2 moves each to the Manhattan distance, and the hint stays honest. And a search that does not store positions: Richard Korf's IDA* (1985) does a depth-first search with a threshold on g + h and raises the threshold until it finds a solution. Korf wrote that it was the only known algorithm that finds optimal solutions of random fifteen puzzles within practical resource limits.
5+Solution
6Complexity
In the worst case A* is the same traversal of the position space: time and memory are proportional to the number of positions taken from the heap, times the log of that number. The hint does not change the order of growth, it changes the base: there are many times fewer positions with g + h at most the answer than positions at the distance of the answer. The solvability check is O(1): 15 tiles, 105 pairs.
7Common mistakes
- Only the hint in the heap key. A greedy search, with answers several times larger than the real ones.
- No parity check. On an unsolvable position the search will go through 1013 positions and fit in neither the time nor the memory.
- A hint that counts the empty cell. If you also add the distance of the empty cell to its place, the hint overestimates: one move shifts both a tile and the empty cell. In a position one move from solved such a hint says 2, and A* no longer guarantees the shortest answer.
- Positions as lists. A list cannot be a key of a Python dictionary or set; you need a tuple.