计算 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)

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

Calculate Manhattan distance for n_puzzle problem?

python

artificial-intelligence

manhattan