title: How is Manhattan distance an admissible heuristic?
body: <p>Ain't it true that while counting the moves for 1 tile can lead to other tiles getting to their goal state? And hence counting for each tile can give us a count more than the minimum moves required to reach the goal state?</p>
  
  <p>This question is in context of Manhattan distance for 15-Puzzle.</p>
  
  <p>Here is the Question in different words:</p>
  
  <p>Can we use Manhattan distance as an admissible heuristic for N-Puzzle. To implement A* search we need an admissible heuristic. Is Manhattan heuristic a candidate? If yes, how do you counter the above argument (the first 3 sentences in the question)?</p>
  
  <p>Definitions:  <a href="http://en.wikipedia.org/wiki/A*" rel="noreferrer">A*</a> is a kind of search algorithm.  It uses a heuristic function to determine the estimated distance to the goal.  As long as this heuristic function never overestimates the distance to the goal, the algorithm will find the shortest path, probably faster than breadth-first search would.  A heuristic that satisfies that condition is <em>admissible</em>.</p>