Course contentsShow
← Computer Science
Lesson 2756 of 2,87261. AI and Search AlgorithmsFree lesson

Manhattan Distance Heuristic

Apply Manhattan distance as a heuristic for grid-based pathfinding problems.

Manhattan Distance Heuristic

You'll learn: How to apply Manhattan distance as a powerful admissible heuristic for grid-based pathfinding problems.

What Is Manhattan Distance?

Manhattan distance measures the distance between two points on a grid by counting only horizontal and vertical moves—no diagonals. Imagine navigating city blocks in Manhattan, where you can't cut through buildings: you must walk along streets (horizontal) and avenues (vertical).

For two points (x₁, y₁) and (x₂, y₂), the Manhattan distance is:

h(n) = |x₁ - x₂| + |y₁ - y₂|

Why Use It as a Heuristic?

In grid-based pathfinding problems like sliding tile puzzles or maze navigation with four-directional movement, Manhattan distance provides an admissible heuristic for A* search. It never overestimates the actual cost to reach the goal because:

  1. You must make at least |Δx| horizontal moves
  2. You must make at least |Δy| vertical moves
  3. No shortcut through obstacles can reduce these minimum moves

Example: 8-Puzzle

In an 8-puzzle, calculate each tile's Manhattan distance from its current position to its goal position, then sum them all:

Current:  1 2 3     Goal:  1 2 3
          4 _ 6            4 5 6
          7 5 8            7 8 _

Tile 5: |2-1| + |1-2| = 2
Tile 6: |2-1| + |2-2| = 1
Tile 8: |2-2| + |2-0| = 2
h(state) = 2 + 1 + 2 = 5

This tells A* that we need at least 5 more moves—guiding the search efficiently toward the goal without ever being overly optimistic.

Key Takeaway: Manhattan distance is an admissible, easy-to-compute heuristic for grid-based problems with axis-aligned movement, making it ideal for guiding A* search efficiently.