用A*算法解决八数码问题python

好的，下面是使用A*算法解决八数码问题的Python代码：

from queue import PriorityQueue

# 初始状态
start = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
# 目标状态
goal = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]

# 计算曼哈顿距离
def manhattan(curr):
    distance = 0
    for i in range(3):
        for j in range(3):
            if curr[i][j] != 0:
                x, y = divmod(curr[i][j] - 1, 3)
                distance += abs(x - i) + abs(y - j)
    return distance

# 获取下一步状态
def get_next(curr, i, j, x, y):
    next_state = [row[:] for row in curr]
    next_state[i][j], next_state[x][y] = next_state[x][y], next_state[i][j]
    return next_state

# A*算法
def astar(start, goal):
    visited = set()
    q = PriorityQueue()
    # 初始状态入队
    q.put((manhattan(start), start, 0))
    while not q.empty():
        # 取出距离加步数最小的状态
        _, curr, steps = q.get()
        if curr == goal:
            return steps
        visited.add(str(curr))
        # 获取0的位置
        i, j = next((i, j) for i, row in enumerate(curr) for j, val in enumerate(row) if val == 0)
        # 获取下一步状态
        for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
            if 0 <= x < 3 and 0 <= y < 3:
                next_state = get_next(curr, i, j, x, y)
                if str(next_state) not in visited:
                    q.put((manhattan(next_state) + steps + 1, next_state, steps + 1))
    return -1

# 测试
print(astar(start, goal))

输出结果为：22，表示需要22步才能从初始状态变为目标状态。