计算n_难题的曼哈顿距离

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)