用A*算法求解八数码问题的源代码

A*算法是一种启发式搜索算法，用于解决许多问题，包括八数码问题。下面是使用A*算法求解八数码问题的Python源代码示例：

import heapq

def get_manhattan_distance(board):
    """
    计算当前棋盘状态和目标状态的曼哈顿距离
    """
    distance = 0
    for i in range(3):
        for j in range(3):
            if board[i][j] != 0:
                x, y = divmod(board[i][j]-1, 3)
                distance += abs(x-i) + abs(y-j)
    return distance

def get_successors(board):
    """
    获取当前棋盘状态的所有合法后继状态
    """
    successors = []
    for i in range(3):
        for j in range(3):
            if board[i][j] == 0:
                if i > 0:
                    new_board = [row[:] for row in board]
                    new_board[i][j], new_board[i-1][j] = new_board[i-1][j], new_board[i][j]
                    successors.append(new_board)
                if i < 2:
                    new_board = [row[:] for row in board]
                    new_board[i][j], new_board[i+1][j] = new_board[i+1][j], new_board[i][j]
                    successors.append(new_board)
                if j > 0:
                    new_board = [row[:] for row in board]
                    new_board[i][j], new_board[i][j-1] = new_board[i][j-1], new_board[i][j]
                    successors.append(new_board)
                if j < 2:
                    new_board = [row[:] for row in board]
                    new_board[i][j], new_board[i][j+1] = new_board[i][j+1], new_board[i][j]
                    successors.append(new_board)
                return successors

def a_star(start, goal):
    """
    A*算法求解八数码问题
    """
    heap = [(get_manhattan_distance(start), start)]
    visited = set()
    while heap:
        (distance, current) = heapq.heappop(heap)
        if current == goal:
            return current
        visited.add(str(current))
        for successor in get_successors(current):
            if str(successor) not in visited:
                heapq.heappush(heap, (get_manhattan_distance(successor) + distance + 1, successor))
    return None

# 测试代码
start = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
goal = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
result = a_star(start, goal)
if result is not None:
    print("Found a solution!")
    for row in result:
        print(row)
else:
    print("No solution found.")