八数码问题python代码

以下是一个八数码问题的 Python 代码示例：

from queue import PriorityQueue

class Board:
    def __init__(self, board, moves=0, previous=None):
        self.board = board
        self.moves = moves
        self.previous = previous

    def __lt__(self, other):
        return self.moves < other.moves

    def __eq__(self, other):
        return self.board == other.board

    def __hash__(self):
        return hash(str(self.board))

    def get_blank_pos(self):
        for i in range(3):
            for j in range(3):
                if self.board[i][j] == 0:
                    return i, j

    def get_neighbors(self):
        i, j = self.get_blank_pos()
        neighbors = []
        if i > 0:
            new_board = [row[:] for row in self.board]
            new_board[i][j], new_board[i-1][j] = new_board[i-1][j], new_board[i][j]
            neighbors.append(Board(new_board, self.moves+1, self))
        if i < 2:
            new_board = [row[:] for row in self.board]
            new_board[i][j], new_board[i+1][j] = new_board[i+1][j], new_board[i][j]
            neighbors.append(Board(new_board, self.moves+1, self))
        if j > 0:
            new_board = [row[:] for row in self.board]
            new_board[i][j], new_board[i][j-1] = new_board[i][j-1], new_board[i][j]
            neighbors.append(Board(new_board, self.moves+1, self))
        if j < 2:
            new_board = [row[:] for row in self.board]
            new_board[i][j], new_board[i][j+1] = new_board[i][j+1], new_board[i][j]
            neighbors.append(Board(new_board, self.moves+1, self))
        return neighbors

    def is_solved(self):
        return self.board == [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

    def get_path(self):
        path = []
        current = self
        while current:
            path.append(current)
            current = current.previous
        return path[::-1]

def solve(board):
    start = Board(board)
    frontier = PriorityQueue()
    frontier.put(start)
    visited = set()
    while not frontier.empty():
        current = frontier.get()
        if current.is_solved():
            return current.get_path()
        visited.add(current)
        for neighbor in current.get_neighbors():
            if neighbor not in visited:
                frontier.put(neighbor)
    return None

board = [[1, 2, 3], [4, 5, 6], [7, 0, 8]]
path = solve(board)
if path:
    for board in path:
        for row in board.board:
            print(row)
        print()
else:
    print("No solution found")

这个代码使用了 A* 搜索算法来解决八数码问题。它定义了一个 `Board` 类来表示一个棋盘状态，其中包括棋盘的布局、移动步数和前一个状态。它还定义了一些方法来获取空格位置、获取邻居状态、判断是否已经解决、获取路径等。`solve` 函数使用优先队列来进行搜索，直到找到解决方案或者无解为止。如果找到了解决方案，它将返回一个包含路径的列表，否则返回 `None`。最后，它打印出了路径中的每个状态。