a*八数码问题python代码

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

import heapq

class PuzzleState:
    def __init__(self, board, parent=None, move=""):
        self.board = board
        self.parent = parent
        self.move = move
        self.depth = 0
        if parent:
            self.depth = parent.depth + 1

    def __str__(self):
        return "\n".join([ " ".join(map(str, row)) for row in self.board ])

    @property
    def is_solved(self):
        return str(self) == "1 2 3\n4 5 6\n7 8 0"

    @property
    def cost(self):
        return self.depth + self.heuristic_cost

    @property
    def heuristic_cost(self):
        return sum([ 1 if self.board[i][j] != 0 and self.board[i][j] != (3*i + j + 1) else 0 for i in range(3) for j in range(3) ])

    @property
    def possible_moves(self):
        row, col = next((i, j) for i in range(3) for j in range(3) if self.board[i][j] == 0)
        moves = []
        if row > 0:
            moves.append("U")
        if row < 2:
            moves.append("D")
        if col > 0:
            moves.append("L")
        if col < 2:
            moves.append("R")
        return moves

    def move_to(self, move):
        row, col = next((i, j) for i in range(3) for j in range(3) if self.board[i][j] == 0)
        new_board = [[val for val in row] for row in self.board]
        if move == "U":
            new_board[row][col] = new_board[row-1][col]
            new_board[row-1][col] = 0
        elif move == "D":
            new_board[row][col] = new_board[row+1][col]
            new_board[row+1][col] = 0
        elif move == "L":
            new_board[row][col] = new_board[row][col-1]
            new_board[row][col-1] = 0
        elif move == "R":
            new_board[row][col] = new_board[row][col+1]
            new_board[row][col+1] = 0
        return PuzzleState(new_board, parent=self, move=move)

def solve(puzzle):
    queue = []
    heapq.heappush(queue, (puzzle.cost, puzzle))
    visited = set()
    while queue:
        _, current = heapq.heappop(queue)
        if current.is_solved:
            moves = []
            while current.parent:
                moves.append(current.move)
                current = current.parent
            return moves[::-1]
        visited.add(str(current))
        for move in current.possible_moves:
            next_state = current.move_to(move)
            if str(next_state) not in visited:
                heapq.heappush(queue, (next_state.cost, next_state))
    return None

puzzle = PuzzleState([[2, 3, 6], [1, 5, 0], [7, 8, 4]])
print("\n".join([ " ".join(map(str, row)) for row in puzzle.board ]))
print()
for move in solve(puzzle):
    print(move)
    puzzle = puzzle.move_to(move)
    print("\n".join([ " ".join(map(str, row)) for row in puzzle.board ]))
    print()

这个代码使用了 `PuzzleState` 类来表示八数码问题的状态，其中包括了当前的棋盘布局、父状态、移动方向和深度。`is_solved` 方法用于判断当前状态是否已经达到目标状态，`cost` 方法用于计算当前状态的总代价，包括深度和启发式代价，`heuristic_cost` 方法则用于计算当前状态的启发式代价，这里采用了曼哈顿距离作为启发式函数。`possible_moves` 方法返回当前状态可以进行的移动方向，`move_to` 方法则根据指定的移动方向生成新的状态。

`solve` 函数使用 A* 算法来求解八数码问题。它使用了一个优先队列来维护待扩展的状态，每次从队列中取出代价最小的状态进行扩展。如果扩展得到的状态已经是目标状态，就返回从初始状态到达该状态的移动方向序列。否则，将该状态加入已访问的集合中，并根据可能的移动方向生成新的状态加入优先队列中。

这个代码使用了 `heapq` 模块来实现优先队列，它采用了小根堆的方式来维护队列。在每个状态中，我们使用字符串形式的棋盘布局来表示状态，这样可以方便地进行比较和哈希。