Calculating the Manhattan distance in the eight puzzle

Question

I am working on a program to solve the Eight Puzzle in Python using informed search w/ heuristics. The heuristic we are supposed to use is the Manhattan distance. So for a board like:

 State            Goal        Different Goal
7  2  4         1  2  3           1  2  3
5     6         8     4           4  5  6
8  3  1         7  6  5           7  8

The Manhattan distance would be 4 + 0 + 3 + 3 + 1 + 0 + 2 + 1 = 14

Visually, it is easy to count how many spaces away a certain number is, but in Python I am representing a board as a list, so the board above would be [7, 2, 4, 5, 0, 6, 8, 3, 1] and the goal state would be [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]. I've been messing around trying to get this to work using mod but can't seem to get it working properly. My teacher said using mod would be helpful in figuring out how to do this. Some examples I looked at used a 2d array for the abs(x_val - x_goal) + abs(y_val - y_goal) which makes sense, but since I am using a list I am not sure how to implement this. The code I got so far is:

distance = 0
xVal = 0
yVal = 0
for i in range(len(self.layoutList)):
    pos = self.layoutList.index(i)
    if pos i == 0 or pos i == 1 or pos i == 2:
        xVal = pos
        yVal = 0
    if pos i == 3 or pos i == 4 or pos i == 5:
        xVal = pos - 3
        yVal = 1
    if pos i == 6 or pos i == 7 or pos i == 8:
        xVal = pos - 6
        yVal = 2

This would generate an x, y value for each tile. So the state above represented as [7, 2, 4, 5, 0, 6, 8, 3, 1] would generate (0, 0) for 7, (2, 0) for 4, etc. I would implement this the same way for the goalstate to get the x,y coordinates for that. Then I would take the absolute value of the x-val - x_goal and whatnot. But is there a better/more efficient way of doing this from the list directly instead of using 2 for loops to iterate both lists?

Answer 1

Summing over each number's Manhatten distance:

>>> board = [7, 2, 4, 5, 0, 6, 8, 3, 1]
>>> sum(abs((val-1)%3 - i%3) + abs((val-1)//3 - i//3)
        for i, val in enumerate(board) if val)
14

For example, the 7 belongs at (zero-based) coordinate (0, 2) = ((7-1)%3, (7-1)//3) but is at coordinate (0, 0), so add abs(0 - 0) + abs(2 - 0) for it.

For non-standard goals:

>>> goal = [1, 2, 3, 8, 0, 4, 7, 6, 5]
>>> sum(abs(b%3 - g%3) + abs(b//3 - g//3)
        for b, g in ((board.index(i), goal.index(i)) for i in range(1, 9)))
16