@@ -0,0 +1,1012 @@
+%22%22%22%0Apynpuzzle - Solve n-puzzle with Python%0A%0AA* tree search algorithm using manhattan distance heuristic%0A%0AVersion : 1.0.0%0AAuthor : Hamidreza Mahdavipanah%0ARepository: http://github.com/mahdavipanah/pynpuzzle%0ALicense : MIT License%0A%22%22%22%0Aimport heapq%0Afrom .util import best_first_seach as bfs%0A%0A%0Adef search(state, goal_state):%0A    %22%22%22A* tree search using manhattan distance heuristic%22%22%22%0A%0A    def gn(node):%0A        return node.gn()%0A%0A    tiles_places = %5B%5D%0A    for i in range(len(goal_state)):%0A        for j in range(len(goal_state)):%0A            heapq.heappush(tiles_places, (goal_state%5Bi%5D%5Bj%5D, (i, j)))%0A%0A    def hn(node):%0A        cost = 0%0A        for i in range(len(node.state)):%0A            for j in range(len(node.state)):%0A                tile_i, tile_j = tiles_places%5Bnode.state%5Bi%5D%5Bj%5D%5D%5B1%5D%0A                if i != tile_i or j != tile_j:%0A                    cost += abs(tile_i - i) + abs(tile_j - j)%0A        return cost%0A%0A    def fn(node):%0A        return gn(node) + hn(node)%0A%0A    return bfs.search(state, goal_state, fn)%0A

Add a* tree search algorithm using manhattan distance heuristic