GenericUser01 - 11 months ago 109

Python 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]`

`[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]`

`abs(x_val - x_goal) + abs(y_val - y_goal)`

`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]`

`(0, 0)`

`(2, 0)`

Answer Source

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
```