Calculate Manhattan distance for n_puzzle problem?

Question

I'm trying to calculate for each tile in a n_puzzle problem where the tile is misplaced, find the number of moves required to reach the correct location.

E.g. 3x3 grid, if tile 1 was in the top left (0,0) where it should be bottom right (2,2), it would take 4 moves to reach the goal.

I'm saving the puzzle in the form [0, 0, [0, 1, 2], [3, 4, 5], [6, 7, 8]] where the first two values represent the coordinates of the blank tile zero. What I have so far is a method that calculates how many tiles are misplaced:

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

Any advice would be much appreciated!

Answer 1

Let's say the misplace tile is in position (x, y), while the correct position should be (w, z). The number of moves required to move the tile to the correct position is:

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