计算n_puzzle问题的曼哈顿距离？

Question

我正在尝试计算n_puzzle问题中的每个瓦片，其中瓦片被放错了位置，找到到达正确位置所需的移动次数。

例如，3x3网格，如果瓷砖1在左上角(0,0)，而它应该在右下角(2,2)，它将需要4步才能到达目标。

我将拼图保存为表单[0, 0, [0, 1, 2], [3, 4, 5], [6, 7, 8]]，其中前两个值表示空白块零的坐标。到目前为止，我有一个计算放错了多少块的方法：

def GetDist(self):
    if self.value == self.goal:
        return 0
    dist = 0
    for a, b in zip(self.value[2], self.goal[2]):
        for g, t in zip(a, b):
            if g != t:
                dist += 1
    return dist

任何建议都将不胜感激！

Answer 1

假设错位的瓦片在位置(x，y)，而正确的位置应该是(w，z)。将平铺移动到正确位置所需的移动次数为：

n_moves = abs(x - w) + abs(y - z)