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

Manhattan distance is the taxi distance in road similar to those in Manhattan. You are right with your formula

distance += abs(x_value - x_goal) + abs(y_value - y_goal)

where x_value, y_value is where you are and x_goal, y_goal is where you want to go.

This implementation using mhd uses this heuristic: the mhd between the point defined by the indices of each of '12346578' in current position and the point defined by the indices of each of '12346578' in goal

def h(self, node):
    """Heuristic for 8 puzzle: returns sum for each tile of manhattan
    distance between it's position in node's state and goal"""
    sum = 0
    for c in '12345678':
        sum =+ mhd(node.state.index(c), self.goal.index(c))
    return sum

Didnt try yet. Maybe link is of some help.

Answer 2

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