Calculating Manhattan Distance in Python in an 8-Puzzle Game

Calculating the Manhattan distance in the eight puzzle

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

Is there a more efficient algorithm to calculate the Manhattan distance of a 8-puzzle game?

It looks to me like you should only need to calculate the full Manhattan distance sum for an entire board once - for the first board. After that, you're creating new Board entities from existing ones by swapping two adjacent numbers. The total Manhattan distance on the new board will differ only by the sum of changes in Manhattan distance for these two numbers.

If one of the numbers is the blank (0), then the total distance changes by minus one or one depending on whether the non-blank number moved closer to its proper place or farther from it. If both of the numbers are non-blank, as when you're making "twins", the total distance changes by minus two, zero, or two.

Here's what I would do: add a manhattan_distance = None argument to Board.__init__. If this is not given, calculate the board's total Manhattan distance; otherwise simply store the given distance. Create your first board without this argument. When you create a new board from an existing one, calculate the change in the total distance and pass the result in to the new board. (The cached_manhattan becomes irrelevant.)

This should reduce the total number of calculations involved with distance by quite a bit - I'd expect it to speed things up by several times, more the larger your board size.

8 Puzzle Game - finding position in 2d array

Manhattan could using a reverse lookup table.

Code

def manhattan_distance(self, other):
    ' Distance between where tiles are and where they should be  '
    
    # Generate reverse lookup table so we know where each item should be located
    lookup_loc = {}
    if i in range(3):
        for j in range(3):
            # other.board[i][j] is the value
            # which has location at (i, j)
            lookup_loc[other.board[i][j]] = (i, j)
          
    dist = 0
    for i in range(3):
        for j in range(3):
            if self.board[i][j] != other.board[i][j]:
                # Find correct location for value self.board[i][j]
                correct_loc = lookup_loc[self.board[i][j]]

                # Manhattan distance between current location (i, j) and
                # correction location
                dist += abs(correct_loc[0]-i) + abs(correct_loc[1] - j)
    return dist

Calculate Manhattan distance for n_puzzle problem?

Let's say the misplace tile is in position (x, y), while the correct position should be (w, z). The number of moves required to move the tile to the correct position is:

n_moves = abs(x - w) + abs(y - z)

Manhattan distance in A*

I was stuck in the same place sometime back where I was solving this in 17 moves.The problem was that I was only using heuristic h(n) for the A* algorithm and whereas for choosing the next node A* uses manhattan distance(heuristic) + pathcost (cost to reach the node from root called as g(n)) to make the choice.
Once you plug in this to the algorithm it works like a charm.

Hope this helps someone who is stuck in the same place.

8Puzzle game with A* : What structure for the open set?

The open set should be a priority queue. Typically these are implemented using a binary heap, though other implementations exist.

Neither an array-list nor a dictionary would be efficient.

---

The closed set should be an efficient set, so usually a hash table or binary search tree, depending on what your language's standard library defaults to.

A dictionary (aka "map") would technically work, but it's conceptually the wrong data-structure because you're not mapping to anything. An array-list would not be efficient.

---

Related Topics