A*搜索求解8数码问题的python实现代码

下面是一份基于Python的A*搜索算法求解八数码问题的代码实现：

from queue import PriorityQueue

class Puzzle:
    def __init__(self, init_state, goal_state):
        self.init_state = init_state
        self.goal_state = goal_state

    def get_blank_pos(self, state):
        for row in range(3):
            for col in range(3):
                if state[row][col] == 0:
                    return (row, col)

    def get_children(self, state):
        children = []
        blank_pos = self.get_blank_pos(state)
        moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for move in moves:
            new_row = blank_pos[0] + move[0]
            new_col = blank_pos[1] + move[1]
            if 0 <= new_row < 3 and 0 <= new_col < 3:
                new_state = [row[:] for row in state]
                new_state[blank_pos[0]][blank_pos[1]] = new_state[new_row][new_col]
                new_state[new_row][new_col] = 0
                children.append(new_state)
        return children

    def get_heuristic(self, state):
        distance = 0
        for row in range(3):
            for col in range(3):
                if state[row][col] != 0:
                    goal_row = (state[row][col] - 1) // 3
                    goal_col = (state[row][col] - 1) % 3
                    distance += abs(row - goal_row) + abs(col - goal_col)
        return distance

    def solve(self):
        open_list = PriorityQueue()
        open_list.put((0, self.init_state))
        closed_list = set()
        moves = []
        while not open_list.empty():
            current = open_list.get()[1]
            if current == self.goal_state:
                while current != self.init_state:
                    blank_pos = self.get_blank_pos(current)
                    for move in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        new_row = blank_pos[0] + move[0]
                        new_col = blank_pos[1] + move[1]
                        if 0 <= new_row < 3 and 0 <= new_col < 3:
                            new_state = [row[:] for row in current]
                            new_state[blank_pos[0]][blank_pos[1]] = new_state[new_row][new_col]
                            new_state[new_row][new_col] = 0
                            if self.get_heuristic(new_state) < self.get_heuristic(current):
                                current = new_state
                                moves.append(current)
                                break
                return moves[::-1]
            closed_list.add(str(current))
            for child in self.get_children(current):
                if str(child) not in closed_list:
                    priority = len(moves) + self.get_heuristic(child)
                    open_list.put((priority, child))
                    closed_list.add(str(child))
        return None

init_state = [[1, 2, 3], [4, 0, 5], [6, 7, 8]]
goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
puzzle = Puzzle(init_state, goal_state)
moves = puzzle.solve()
if moves:
    print(f"Found solution using {len(moves)} moves:")
    for move in moves:
        print(move)
else:
    print("No solution found.")

在上述代码中，首先定义了一个名为`Puzzle`的类，该类包含了解决八数码问题所需的各种方法。然后，定义了初始状态和目标状态，创建了一个`Puzzle`对象，并调用其`solve`方法来解决问题。

在A*算法实现中，使用了优先队列来维护开放列表，并利用集合来维护封闭列表。在每次迭代中，从开放列表中取出具有最小优先级的状态，并将其加入封闭列表。然后，生成当前状态的所有子状态，并将其加入开放列表（前提是该子状态不在封闭列表中）。如果当前状态是目标状态，则回溯路径并返回所有移动步骤；否则，继续迭代，直到找到解决方案或开放列表为空。

最后，输出找到的解决方案（如果存在）。