有没有更有效的算法来计算8拼图游戏的曼哈顿距离？

我目前正在编写一种算法，该算法通过使用Python的A *搜索算法来解决8谜题游戏。但是，当我对代码进行计时时，我发现这get_manhattan_distance花费了很长时间。

我cProfile为Python运行了代码，结果低于该程序输出的结果。这是我的要点。

通过使用Numpy数组而不是Python的列表进行复制，我已经使我的程序更加高效。我不太了解如何使这一步骤更有效率。我当前的代码get_manhattan_distance是

def get_manhattan(self):
    """Returns the Manhattan heuristic for this board

    Will attempt to use the cached Manhattan value for speed, but if it hasn't 
    already been calculated, then it will need to calculate it (which is 
    extremely costly!).
    """
    if self.cached_manhattan != -1:
      return self.cached_manhattan

    # Set the value to zero, so we can add elements based off them being out of
    # place.
    self.cached_manhattan = 0

    for r in range(self.get_dimension()):
      for c in range(self.get_dimension()):
        if self.board[r][c] != 0:
          num = self.board[r][c]

          # Solves for what row and column this number should be in.
          correct_row, correct_col = np.divmod(num - 1, self.get_dimension())

          # Adds the Manhattan distance from its current position to its correct
          # position.
          manhattan_dist = abs(correct_col - c) + abs(correct_row - r)
          self.cached_manhattan += manhattan_dist

    return self.cached_manhattan

其背后的想法是，3x3网格的目标难题如下：

 1  2  3
 4  5  6
 7  8 

有空白图块的地方（该空白图块在int数组中由0表示）。因此，如果我们有一个难题：

 3  2  1
 4  6  5
 7  8   

它的曼哈顿距离应该为6。这是因为3离它应该在的位置两个地方。1离应有的地方两个。5是应该离开的地方，而6是应该离开的地方。因此，2 + 2 + 1 + 1 = 6。

不幸的是，这种计算需要很长时间，因为有成千上万的不同电路板。有什么办法可以加快计算速度吗？