Calculating sum of manhattan distances in a sliding puzzle
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));