CODEWITHSUNDEEP
pythonperformanceheuristics
Aditya Pillai
Aditya Pillai

Reputation: 43

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

I'm currently writing an algorithm that solves the 8-puzzle game through an A* search algorithm with Python. However, when I time my code, I find that get_manhattan_distance takes a really long amount of time.

I ran my code with cProfile for Python, and the results are below what is printed out by the program. Here is a gist for my issue.

I've already made my program more efficient by copying using Numpy Arrays instead of Python's lists. I don't quite know how to make this step more efficient. My current code for get_manhattan_distance is

def get_manhattan(self):
    """Returns the Manhattan heuristic for this board

    Will attempt to use the cached Manhattan value for speed, but if it hasn't 
    already been calculated, then it will need to calculate it (which is 
    extremely costly!).
    """
    if self.cached_manhattan != -1:
      return self.cached_manhattan

    # Set the value to zero, so we can add elements based off them being out of
    # place.
    self.cached_manhattan = 0

    for r in range(self.get_dimension()):
      for c in range(self.get_dimension()):
        if self.board[r][c] != 0:
          num = self.board[r][c]

          # Solves for what row and column this number should be in.
          correct_row, correct_col = np.divmod(num - 1, self.get_dimension())

          # Adds the Manhattan distance from its current position to its correct
          # position.
          manhattan_dist = abs(correct_col - c) + abs(correct_row - r)
          self.cached_manhattan += manhattan_dist

    return self.cached_manhattan

The idea behind this is, the goal puzzle for a 3x3 grid is the following:

 1  2  3
 4  5  6
 7  8

Where there is a blank tile (the blank tile is represented by a 0 in the int array). So, if we have the puzzle:

 3  2  1
 4  6  5
 7  8

It should have a Manhattan distance of 6. This is because, 3 is two places away from where it should be. 1 is two places away from where it should be. 5 is one place away from where it should be, and 6 is one place away from where it should be. Hence, 2 + 2 + 1 + 1 = 6.

Unfortunately, this calculation takes a very long time because there are hundreds of thousands of different boards. Is there any way to speed this calculation up?

Upvotes: 4

Views: 1074

Answers (1)

Nathan Vērzemnieks
Nathan Vērzemnieks

Reputation: 5603

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.

Upvotes: 1

Related Questions