Calculating sum of manhattan distances in a sliding puzzle I would like some feed back on a method which calculates the sum of Manhattan distances for each tile in a sliding puzzle to its goal position in the goal puzzle.

Here is the code:

public static int calcManhattanDistance(int[] ps, int[] goal) {
    int rowSz = calculatePuzzleRowSize(ps);
    int manhattanDistanceSum = 0;
    for (int i = 0; i &lt; ps.length; i++) {
        for (int j = 0; j &lt; ps.length; j++) {
            if (ps[i] == goal[j])
                manhattanDistanceSum += (Math.abs(i/rowSz - j/rowSz) + Math.abs(i%rowSz - j%rowSz)); 
        }
    }
    return manhattanDistanceSum;
}


Please tell me if you think something should be changed or what I can do to increase efficiency.

Here is the calculatePuzzleRowSize(ps) method:

public static int calculatePuzzleRowSize(int[] ps) {
    int sz = ps.length;
    int rowSz = (int) Math.sqrt(sz);
    return rowSz;
}


Here is the newly implemented calculateManhattanDistanceSum

public static int calculateManhattanDistanceSum(int[] ps, int[] goal) {
    int rowSize = (int) Math.sqrt(ps.length);
    int manhattanDistanceSum = 0;
    Map&lt;Integer, Integer&gt; psMap = new HashMap&lt;Integer, Integer&gt;();
    for (int i : ps)
        psMap.put(ps[i], i);
    for (int j : goal)
        manhattanDistanceSum += Math.abs(psMap.get(j)/rowSize - j/rowSize) + Math.abs(psMap.get(j)%rowSize - j%rowSize); 
    return manhattanDistanceSum;
}
Assuming you hold the right order of the puzzle pieces in the goal-array, wouldn't it be natural that the right order itsself is 0 to #pieces - 1?

If that's the case, you could calculate the manhatten distance by just iterating over ps[]:

for (int i = 0; i &lt; ps.length; i++)
    if( ps[i] == i ) continue;
else
    manhattanDistanceSum += (Math.abs(ps[i]/rowSz - i/rowSz) + Math.abs(ps[i]%rowSz - i%rowSz));