title: Can somebody explain in Manhattan dstance for the 8 puzzle in java for me?
body: <p>i am writing an A* algorithm which can solve the 8-puzzle in Java, so far i have implemented DFS, BFS, A* using the number of tiles out of place and i just need to implement it using the heuristic for the Manhattan distance.</p>
  
  <p>As you are probably aware the Manhattan distance is the sum of each tiles displacement in relation to its current position and its index in the goal state.</p>
  
  <p>I have googled around and found these stack over flow topics: </p>
  
  <p><a href="https://stackoverflow.com/questions/8224470/calculating-manhattan-distance">Calculating Manhattan Distance</a>
  <a href="https://stackoverflow.com/questions/12526792/manhattan-distance-in-a">Manhattan distance in A*</a></p>
  
  <p>Which returned the following code:</p>
  
  <pre><code>  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); 
          } 
      }
  </code></pre>
  
  <p>This is what i don't understand, given this board and this goal state:</p>
  
  <p>initial board:</p>
  
  <pre><code> 1,2,5
   3,0,4
   6,7,8
  </code></pre>
  
  <p>goal state:</p>
  
  <pre><code>0,1,2
  3,4,5
  6,7,8
  </code></pre>
  
  <p>if i key in the values for board[0][0], which has the value 1, which happens to be 1 move away from its correct position i get these results:</p>
  
  <pre><code> x = 0;
   y = 0;
   value = 1;
   targetX = (value -1)/3; // 0/3 = 0
   targetY = (value -1)%3 //0%3 = 0
  
   int dx = x - targetX; // 0 - 0
   int dy = y - targetY; // 0 - 0
   manhattanDistanceSum += Math.abs(dx) + Math.abs(dy); 
  </code></pre>
  
  <p>Which produces ultimately 0 + 0, which is obviously incorrect as it should return the value of 1.</p>
  
  <p>Is there another way to it for example:</p>
  
  <pre><code>  for(int i = 0; i &lt; 3 i ++){
       for(int j =0; j &lt; 3; j ++){
          int value = currentBoard[i][j];
          int goalValue = getLocationOfValueInGoalState(value);
  
         /* caluclate the value's X distance away from the returned goal state location   for said value, then do the same for the Y */
  
  
  
  
  
        }
     }
  </code></pre>
  
  <p>Hope someone understands my question, im a bit confused at the moment in all honesty.</p>