Рассчитать манхэттенское расстояние для задачи 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)