GenericUser01 - 1 year ago 149
Python Question

# Calculating the Manhattan distance in the eight puzzle

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?

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download