To calculate Manhattan distance in an 8 puzzle, you sum the total number of horizontal and vertical moves each tile needs to make to reach its correct position in the goal state. This heuristic is widely used for its simplicity and effectiveness in estimating the minimum number of moves required to solve the puzzle.
Understanding Manhattan Distance
Manhattan distance, also known as taxicab geometry or rectilinear distance, measures the distance between two points by summing the absolute differences of their Cartesian coordinates. In the context of an 8 puzzle, it's applied to each numbered tile (excluding the blank space) by determining how many steps left/right and up/down it must move to reach its final, solved position.
Essentially, Manhattan distance is computed by the sum of the distances of each tile from where it should belong. It estimates the number of moves needed to transform a given puzzle state into the solution state.
Why Use Manhattan Distance?
- Heuristic: It serves as an admissible heuristic for search algorithms like A*, meaning it never overestimates the true number of moves required to reach the goal.
- Efficiency: It's relatively easy and quick to compute, making it suitable for evaluating many puzzle states during a search.
- Guidance: It helps guide the search towards the goal state by prioritizing states that are "closer" to the solution.
Step-by-Step Calculation
To calculate the Manhattan distance for an 8 puzzle:
- Identify Current and Goal States: Determine the current arrangement of tiles and the desired goal arrangement.
- Iterate Through Each Tile: For each numbered tile (1 through 8), do the following:
- Find Current Position: Locate the tile's current row and column.
- Find Goal Position: Locate the tile's target row and column in the solved state.
- Calculate Horizontal Distance: Determine the absolute difference between the current column and the goal column.
- Calculate Vertical Distance: Determine the absolute difference between the current row and the goal row.
- Sum Tile Distance: Add the horizontal and vertical distances for that specific tile.
- Aggregate Total Distance: Sum up the individual distances calculated for all tiles. The blank tile (usually represented by 0 or an empty space) is ignored in this calculation.
Practical Example
Let's consider an example with a common goal state where tiles are arranged in ascending order, with the blank space at the bottom right.
Current State:
| 1 | 2 | 3 |
|---|---|---|
| 4 | 0 | 5 |
| 7 | 8 | 6 |
Goal State:
| 1 | 2 | 3 |
|---|---|---|
| 4 | 5 | 6 |
| 7 | 8 | 0 |
(Note: '0' represents the blank tile)
Now, let's calculate the Manhattan distance for each tile:
| Tile | Current Position (Row, Col) | Goal Position (Row, Col) | Horizontal Distance | Vertical Distance | Total Tile Distance |
|---|---|---|---|---|---|
| 1 | (0, 0) | (0, 0) | |0 - 0| = 0 | |0 - 0| = 0 | 0 |
| 2 | (0, 1) | (0, 1) | |1 - 1| = 0 | |0 - 0| = 0 | 0 |
| 3 | (0, 2) | (0, 2) | |2 - 2| = 0 | |0 - 0| = 0 | 0 |
| 4 | (1, 0) | (1, 0) | |0 - 0| = 0 | |1 - 1| = 0 | 0 |
| 5 | (1, 2) | (1, 1) | |2 - 1| = 1 | |1 - 1| = 0 | 1 |
| 6 | (2, 2) | (1, 2) | |2 - 2| = 0 | |2 - 1| = 1 | 1 |
| 7 | (2, 0) | (2, 0) | |0 - 0| = 0 | |2 - 2| = 0 | 0 |
| 8 | (2, 1) | (2, 1) | |1 - 1| = 0 | |2 - 2| = 0 | 0 |
Total Manhattan Distance = 0 + 0 + 0 + 0 + 1 + 1 + 0 + 0 = 2
This means, according to the Manhattan distance heuristic, the current state is 2 moves away from the goal state.
For more information on heuristics and pathfinding, you can explore resources like Wikipedia's article on Manhattan Distance.
