A* is only as good as its heuristic. Good heuristics are admissible, as close to the true cost as possible, and cheap to compute — and the standard way to invent one is to relax the problem.

Two classic 8-puzzle heuristics

Heuristic	Definition	Relaxed problem it solves exactly
`h₁` — misplaced tiles	Number of tiles not in their goal square	A tile can jump anywhere in one move
`h₂` — Manhattan distance	Sum over tiles of \|row − goal row\| + \|col − goal col\|	A tile can move to any adjacent square, even an occupied one

A relaxed problem has more actions, so its optimal cost can only be lower — that is why a heuristic derived from a relaxation is automatically admissible (and consistent).

Python

import heapq

GOAL = (0, 1, 2, 3, 4, 5, 6, 7, 8)         # 0 = blank

def h1(s):                                  # misplaced tiles (the blank doesn't count)
    return sum(1 for i, tile in enumerate(s) if tile and tile != i)

def h2(s):                                  # Manhattan distance
    return sum(abs(i // 3 - t // 3) + abs(i % 3 - t % 3) for i, t in enumerate(s) if t)

def neighbours(s):
    i = s.index(0)
    r, c = divmod(i, 3)
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if 0 <= r + dr < 3 and 0 <= c + dc < 3:
            j = (r + dr) * 3 + c + dc
            t = list(s)
            t[i], t[j] = t[j], t[i]
            yield tuple(t)

def astar(start, h):
    frontier, best, expanded = [(h(start), 0, start)], {start: 0}, 0
    while frontier:
        f, g, s = heapq.heappop(frontier)
        if s == GOAL:
            return g, expanded
        if g > best[s]:
            continue
        expanded += 1
        for t in neighbours(s):
            if g + 1 < best.get(t, 99):
                best[t] = g + 1
                heapq.heappush(frontier, (g + 1 + h(t), g + 1, t))

start = (7, 2, 4,
         5, 0, 6,
         8, 3, 1)
print(h1(start), h2(start))                 # 8 18 ← true cost is 26
print(astar(start, lambda s: 0))            # (26, 162240) ← h = 0 is uniform-cost search
print(astar(start, h1))                     # (26, 44988)
print(astar(start, h2))                     # (26, 4085)

All three find the optimal 26-move solution; Manhattan distance does it with roughly 40× fewer expansions than no heuristic.

Dominance and the effective branching factor

To compare heuristics independently of problem size, compute the effective branching factor b*: the branching factor a uniform tree of depth d would need to contain the N nodes A* expanded. Close to 1 is ideal.

N + 1 = 1 + b* + (b*)² + … + (b*)ᵈ

Python

def effective_branching(n_expanded, depth):
    lo, hi = 1.0, 10.0
    for _ in range(60):                        # bisection
        b = (lo + hi) / 2
        total = sum(b ** i for i in range(depth + 1))
        lo, hi = (b, hi) if total < n_expanded + 1 else (lo, b)
    return round(b, 2)

print(effective_branching(162240, 26))     # 1.52 ← no heuristic
print(effective_branching(44988, 26))      # 1.44 ← misplaced tiles
print(effective_branching(4085, 26))       # 1.3 ← Manhattan distance

Recipes for heuristics

Domain	Admissible heuristic
Grid, 4-way moves	Manhattan distance `\|dx\| + \|dy\|`
Grid, 8-way moves (diagonal cost √2)	Octile distance `max(dx, dy) + (√2 − 1)·min(dx, dy)`
Any-angle / road maps	Euclidean (straight-line) distance
Travelling salesperson	Cost of a minimum spanning tree of unvisited cities

What makes a heuristic admissible? Give one for the 8-puzzle.

Admissible vs consistent?

If h₂ dominates h₁, is h₂ always better?