A heuristic in AI search is a function that estimates how far a state is from the goal, and its quality decides how much work the search does. In a computed test on 200 random solvable states of the 8-puzzle, A* search with the Manhattan-distance heuristic expanded 1,752 states on average, against 17,120 with a count of misplaced tiles, and both returned shortest solutions. A heuristic that overestimates can cut the work further but returns longer solutions than necessary.
Key takeaways
- A heuristic is admissible when it never overestimates the true remaining cost, and A* with an admissible heuristic returns an optimal solution.
- Among admissible heuristics, the one with larger values at every state is the better guide, because it prunes more of the search.
- On 200 random 8-puzzle states, Manhattan distance needed about one tenth of the expansions that misplaced-tile counting needed.
- Overestimating the distance made solutions longer in 89 of the 200 tests, and pure greedy search produced a longer solution in 193 of them.
- Heuristics trade guarantees for speed, so the first question about any heuristic is whether it can overestimate.
What an admissible heuristic promises
Search algorithms explore states in some order. Uniform-cost search orders them by the cost already paid. A* adds a second term, the heuristic estimate of the cost still to come, and always expands the state with the lowest total. The Berkeley CS188 course text defines the safe case: an admissible estimate is "neither negative nor an overestimate," meaning it is never larger than the true cost to the goal from that state. With such an estimate, A* does not skip a cheaper path, because any path through a state is judged no worse than its real cost. The A* method was published by Peter Hart, Nils Nilsson, and Bertram Raphael in IEEE Transactions on Systems Science and Cybernetics in July 1968.
The same course page describes where such estimates usually come from: solving a relaxed problem, which is the original problem with some rules removed. Dropping the rule that tiles cannot pass through each other turns the sliding puzzle into one where every tile walks straight to its place, and the total walking distance is the Manhattan heuristic. It is also true that if one admissible estimate is at least as large as another at every state, it dominates the other and guides the search better.
Worked example: one 8-puzzle state
This is an illustrative state chosen for this article. Its rows are 8, 1, 3 then 4, blank, 2 then 7, 6, 5, and the goal has 1, 2, 3 then 4, 5, 6 then 7, 8, blank. A shortest solution takes 14 moves, found by exhaustive search. The two common estimates compare as follows.
| Tile | Distance to its goal square (rows plus columns) | In the wrong place? |
|---|---|---|
| 8 | 3 | Yes |
| 1 | 1 | Yes |
| 2 | 2 | Yes |
| 6 | 2 | Yes |
| 5 | 2 | Yes |
| 3, 4, 7 | 0 each | No |
| Total | 10 (Manhattan) | 5 (misplaced tiles) |
Both totals are below the true cost of 14, so both are admissible. The Manhattan value is larger, so it dominates, and the counts below show the effect on this state.
What the estimate saves: a computed comparison
The 8-puzzle has 181,440 reachable states, and the longest shortest solution is 31 moves. The average shortest solution over all reachable states is about 22 moves. For the test, a script drew 200 random reachable states with a fixed seed and ran A* with each heuristic, counting states expanded. Results depend on tie-breaking and on how expansions are counted, so the figures are indicative.
| Heuristic | Average states expanded | Expanded on the worked example |
|---|---|---|
| None (cost so far only) | about 100,400 (10 states) | 5,960 |
| Misplaced tiles | 17,120 (200 states) | 301 |
| Manhattan distance | 1,752 (200 states) | 76 |
The first row used only 10 states because the search is slow without guidance, so it is the roughest number. The ordering is the point: each better estimate cuts the work by roughly an order of magnitude on this puzzle.
When the heuristic misleads
Two common failures show up in the same test. In the first, the estimate is multiplied by two, which can overestimate. A* then finished faster but returned a longer-than-necessary solution in 89 of the 200 states, by 3.2 moves on average when it erred. In the second, greedy best-first search ignores the cost so far and follows the estimate alone. It found a longer solution in 193 of the 200 states, averaging about 45 moves against an average optimum of about 22. On the worked example it returned 36 moves where 14 were possible. The Berkeley text notes that greedy search is not guaranteed to be complete or optimal and can behave like a badly guided depth-first search.
Neither failure means such heuristics are useless. When any acceptable answer will do, an inflated estimate is a legitimate trade. The error comes from assuming the answer is optimal when the heuristic gave no such guarantee.
Why memory, not only time, limits A*
The 15-puzzle has about 10.5 trillion reachable states, far more than any machine can store. Richard Korf's 1985 paper in Artificial Intelligence reported a test on 100 random 15-puzzle instances using the Manhattan heuristic. A* ran out of space after about 30,000 stored nodes on his machine and solved none. His iterative-deepening variant, IDA*, which keeps no open or closed lists, solved all 100 with a median time of 30 CPU minutes, an average solution length of 53 moves, and a maximum of 66. The lesson is that a heuristic problem has two budgets, time and memory, and a method can fail on the second first.
Checklist before trusting a heuristic
- Can the estimate ever exceed the true remaining cost? If yes, optimality is not guaranteed.
- Is it computed by relaxing a rule of the real problem, so the bound is easy to argue?
- Is it at least as large as a simpler admissible estimate at every state?
- Is it cheap enough to compute at every state, since an expensive estimate can cost more than it saves?
- What was the test set, and did it include hard instances as well as typical ones?
FAQ
What is a heuristic problem in AI?
It usually means a search problem where an estimate guides the order of exploration, and the difficulty lies in choosing an estimate that is both informative and safe. A poor choice wastes work or returns worse answers.
Is a heuristic the same as a guess?
No. An admissible heuristic is a bound with a proof behind it. A guess has no such guarantee, which is why the two are treated differently in algorithm analysis.
Does machine learning replace hand-designed heuristics?
Learned estimates are used in some systems, but they need the same checks: a learned value that overestimates can mislead search just as a hand-built one can.
Why not always use the largest estimate possible?
Because above the true cost an estimate stops being admissible. The best admissible heuristic is the largest one that still stays at or below the true cost, and finding it is the design problem.
Related reading
- What toy problems like puzzles prove and miss
- Worked examples of problem formulation
- Heuristics in robot navigation
- Route optimization and the traveling salesman problem
More in AI Basics.
Last verified: October 2026
Sources
- Informed Search, CS188 online textbook, University of California, Berkeley, accessed 2026
- A Formal Basis for the Heuristic Determination of Minimum Cost Paths, Hart PE, Nilsson NJ, Raphael B, IEEE Transactions on Systems Science and Cybernetics 4(2), 100-107, July 1968
- Depth-First Iterative-Deepening: An Optimal Admissible Tree Search, Korf RE, Artificial Intelligence 27, 97-109, 1985
- 8-puzzle state counts and search comparison: computed for this article with a short script (illustrative, reproducible with a fixed random seed)