Lesson 3

The crucial ingredient in the \(A^{*}\)-algorithm is the choice of the heuristic \(h(v)\).

For the 15 Puzzle, a standard choice is the Manhattan distance. For each tile, we compute the distance from its current cell to its target cell, counting only horizontal and vertical steps. We then sum these distances over all tiles: \[h(v)=\sum_{i=1}^{15}d_{i},\] where \(d_{i}\) is the Manhattan distance from the current position of tile \(i\) to its final position.

This heuristic is natural because one move changes the position of only one tile by one cell. Hence, if the total Manhattan distance is, say, \(17\), then at least \(17\) moves are needed to solve the puzzle. In particular, the heuristic never overestimates the true remaining distance.

A heuristic with this property is called admissible.