Calculating Manhattan Distance in Python in an 8-Puzzle game

Question

I am trying to code a simple A* solver in Python for a simple 8-Puzzle game. I have represented the goal of my game in this way:

goal = [[1, 2, 3],
        [8, 0, 4], 
        [7, 6, 5]]

My problem is that I don't know how to write a simple Manhattan Distance heuristic for my goal. I know it should be defined as the sum of the distances between a generic state and my goal state. I think I should code something like:

def manhattan_distance(state):
    distance = 0
    for x in xrange(3):
        for y in xrange(3):
            value = state[x][y]
            x_value = x
            y_value = y
            x_goal = ...?
            y_goal = ...?
            distance += abs(x_value - x_goal) + abs(y_value - y_goal)
    return distance

My problem is that I don't have an explicit representation of the coordinates of the pieces in the goal state, so I don't know how to define 'x_goal' and 'y_goal' for the 'value' piece of the board. I am trying to do it using division and module operations, but it's difficult.

Can you give me some hints to define my 'x_goal' and 'y_goal' variables?

Thank you

Answer 1

Most pythonic implementation you can find.

assuming that,

0 1 2

3 4 5

6 7 8

is the goal state... AND,

1 5 3

4 2 6

7 8 9

is the final state.

initial_state = [1,5,3,4,2,6,7,8,0]
goal_state = [0,1,2,3,4,5,6,7,8]
def calculateManhattan(initial_state):
    initial_config = initial_state
    manDict = 0
    for i,item in enumerate(initial_config):
        prev_row,prev_col = int(i/ 3) , i % 3
        goal_row,goal_col = int(item /3),item % 3
        manDict += abs(prev_row-goal_row) + abs(prev_col - goal_col)
    return manDict

I don't know how else to explain this. It just works. Enjoy ! :D