Manhattan distancia es más de estimación y me vuelve loco

Estoy implementando algoritmo a-star con Distancia de Manhattan para resolver el 8-puzzle (en C). Parece funcionar muy bien y pasa muchas pruebas unitarias, pero no logra encontrar el camino más corto en un caso (encuentra 27 pasos en lugar de 25).

Cuando cambio la función heurística a Hamming distance se encuentra en 25 pasos. También se encuentra en 25 pasos cuando hago la función de distancia de Manhattan para devolver la mitad de la coste.

Es por eso que creo que el problema se encuentra en algún lugar de la función de distancia de Manhattan y es sobre estimar el costo (por lo tanto inadmisible). Pensé que tal vez algo más está yendo mal en el programa C, así que escribí un pequeño script de Python para probar y verificar la salida de la función de distancia de Manhattan y ambos producen exactamente el mismo resultado.

Estoy realmente confundido porque la función heurística parece ser el único punto de falla y parece ser correcta en al mismo tiempo.

Puedes probar este solucionador y poner el orden de baldosas como " 2,6,1,0,7,8,3,5,4" Elija el algoritmo Manhattan distance y se encuentra en 25 pasos. Ahora cámbielo a distancia de Manhattan + conflicto lineal y encontrará 27 pasos.

Pero mi distancia de Manhattan (sin conflicto lineal) se encuentra en 27 pasos.

Aquí está mi algoritmo general:

manhattan_distance = 0
iterate over all tiles
if the tile is not the blank tile:
find the coordinates of this tile on the goal board
manhattan_distance += abs(x - goal_x) + abs(y - goal_y)

Creo que si hubiera algo muy mal con alguna parte importante que no pasaría todas las 25 + pruebas anteriores por lo que esto podría ser algún tipo de caso de borde.

Aquí está la función de distancia de Manhattan comentada en C:

int ManhattanDistance(Puzzle p, State b){
   State goal = getFinalState(p);
   int size = getSize(b);
   int distance = 0;
   if (getSize(goal) == size){ // both states are the same size
      int i, j;
      for(i=0; i<size; i++){
         for(j=0; j<size; j++){ // iterate over all tiles
            int a = getStateValue(b, i, j); // what is the number on this tile?
            if (a != 'B'){ // if it's not the blank tile
               int final_cordinates[2];
               getTileCoords(goal, a, final_cordinates); // find the coordinates on the other board
               int final_i = final_cordinates[0];
               int final_j = final_cordinates[1];
               distance +=  abs(i - final_i) + abs(j - final_j);
            }
         }
      }
   }
   return distance;
}

Por favor ayúdame.

EDITAR: Como se discutió en los comentarios, el código proporcionado para abrir nodos se puede encontrar aquí