title: Manhattan distance in A*
body: <p>I am implementing a NxN puzzle solver using A* search algorithm and using Manhattan distance as a heuristic and I've run into a curious <em>bug</em> (?) which I can't wrap my head around.</p>
  
  <p>Consider these puzzles (0 element being blank space):<br>
  (initial)</p>
  
  <p><code>1 0 2</code><br>
  <code>7 5 4</code><br>
  <code>8 6 3</code><br></p>
  
  <p>(goal)</p>
  
  <p><code>1 2 3</code><br>
  <code>4 5 6</code><br>
  <code>7 8 0</code></p>
  
  <p>The minumum number of moves to reach solution from initial state is 11. However, my solver, reaches goal in 17 moves.</p>
  
  <p>And therein lies the problem - my puzzle solver mostly solves the solvable puzzles in a correct (minimum) number of moves but for this particular puzzle, my solver overshoots the minimum number of moves and I think I've nailed down the problem to a miscalculation of Manhattan distance in this particular case.</p>
  
  <p>At this <a href="http://www.freeimagehosting.net/xn5b8" rel="noreferrer">link</a> you can see what my solver is doing (on the right) and what a tried-n-tested solver is doing (Brian Borowski's excellent solver, available <a href="http://www.brian-borowski.com/Software/Puzzle/" rel="noreferrer">here</a>).</p>
  
  <p>In the very first move, Brian's solver immediately chooses solution that pushes element 5 up, but my solver has other ideas, and on the stacktrace (given on the <a href="http://www.freeimagehosting.net/xn5b8" rel="noreferrer">link</a>), my solver chooses solution which pushes 2 to the left (since that board's Manhattan distance is lower, the board is on the front of priority queue). 
  I can't see what is the problem and I can't blame my Manhattan distance calculation, since it correctly solves a number of other 3x3 puzzles.</p>
  
  <p>Here is how I calculate the Manhattan distance of a given Board:</p>
  
  <pre><code>/**
   * Calculates sum of Manhattan distances for this board and stores it in private field to promote immutability.
   */
  private void calculateManhattanDistance() {
      int manhattanDistanceSum = 0;
      for (int x = 0; x &lt; N; x++) // x-dimension, traversing rows (i)
          for (int y = 0; y &lt; N; y++) { // y-dimension, traversing cols (j)
              int value = tiles[x][y]; // tiles array contains board elements
              if (value != 0) { // we don't compute MD for element 0
                  int targetX = (value - 1) / N; // expected x-coordinate (row)
                  int targetY = (value - 1) % N; // expected y-coordinate (col)
                  int dx = x - targetX; // x-distance to expected coordinate
                  int dy = y - targetY; // y-distance to expected coordinate
                  manhattanDistanceSum += Math.abs(dx) + Math.abs(dy); 
              } 
          }
      manhattanDistance = manhattanDistanceSum;
  }
  </code></pre>
  
  <p>I would appreciate any insight or idea you may have.</p>
  
  <p>If any additional code is needed, I'll post it right away.</p>