用A*算法解决八代码问题的程序python

以下是使用A*算法解决八数码问题的Python程序：

from queue import PriorityQueue

class Board:
    def __init__(self, board, moves=0, goal=None):
        self.board = board
        self.moves = moves
        self.goal = goal
        
    @property
    def heuristic(self):
        return sum(abs(b%3 - g%3) + abs(b//3 - g//3)
                   for b, g in ((self.board.index(i), self.goal.index(i)) for i in range(1, 9)))
        
    @property
    def solved(self):
        return self.board == self.goal
    
    def neighbors(self):
        board = self.board
        i = board.index(0)
        if i in (3, 4, 5, 6, 7, 8):
            b = Board(list(board))
            b.board[i], b.board[i-3] = b.board[i-3], b.board[i]
            yield b
        if i in (0, 1, 2, 3, 4, 5):
            b = Board(list(board))
            b.board[i], b.board[i+3] = b.board[i+3], b.board[i]
            yield b
        if i in (1, 2, 4, 5, 7, 8):
            b = Board(list(board))
            b.board[i], b.board[i-1] = b.board[i-1], b.board[i]
            yield b
        if i in (0, 1, 3, 4, 6, 7):
            b = Board(list(board))
            b.board[i], b.board[i+1] = b.board[i+1], b.board[i]
            yield b
        
    def __lt__(self, other):
        return self.heuristic + self.moves < other.heuristic + other.moves
    
    def __eq__(self, other):
        return self.board == other.board
    
def solve(initial_board):
    queue = PriorityQueue()
    queue.put(Board(initial_board))
    moves = 0
    visited = set()
    while not queue.empty():
        board = queue.get()
        if board.solved:
            return board.moves
        visited.add(board)
        for neighbor in board.neighbors():
            if neighbor not in visited:
                neighbor.moves = board.moves + 1
                queue.put(neighbor)
    raise ValueError('No solution found')
    
if __name__ == '__main__':
    puzzle = [1, 2, 3, 0, 4, 6, 7, 5, 8]
    print(solve(puzzle))

在这个程序中， `Board` 类表示一个八数码状态，并且包含了它的当前状态和目标状态、移动步数、以及启发式估计值。 `heuristic` 属性使用曼哈顿距离来计算当前状态和目标状态之间的距离。 `solved` 属性检查当前状态是否已经与目标状态匹配。 `neighbors` 方法返回所有可能的移动。 `solve` 函数使用优先级队列来实现 A* 算法搜索。程序的输出将是解决这个问题所需的最少移动步数。