a*八数码问题python代码

以下是一个基于A*算法的八数码问题的Python代码示例：

from queue import PriorityQueue

class Puzzle:
    def __init__(self, board):
        self.board = board
        self.goal = [1,2,3,4,5,6,7,8,0]

    def get_new_board(self, board, pos, move):
        new_board = board[:]
        if move == 'left':
            new_board[pos], new_board[pos-1] = new_board[pos-1], new_board[pos]
        elif move == 'right':
            new_board[pos], new_board[pos+1] = new_board[pos+1], new_board[pos]
        elif move == 'up':
            new_board[pos], new_board[pos-3] = new_board[pos-3], new_board[pos]
        elif move == 'down':
            new_board[pos], new_board[pos+3] = new_board[pos+3], new_board[pos]
        return new_board

    def get_possible_moves(self, board):
        pos = board.index(0)
        moves = []
        if pos % 3 > 0:
            moves.append('left')
        if pos % 3 < 2:
            moves.append('right')
        if pos > 2:
            moves.append('up')
        if pos < 6:
            moves.append('down')
        return moves

    def get_score(self, board):
        score = 0
        for i in range(9):
            if board[i] != 0 and board[i] != self.goal[i]:
                score += 1
        return score

    def solve(self):
        count = 0
        open_queue = PriorityQueue()
        open_queue.put((self.get_score(self.board), self.board, count))
        while not open_queue.empty():
            current_score, current_board, count = open_queue.get()
            if current_board == self.goal:
                return count
            for move in self.get_possible_moves(current_board):
                new_board = self.get_new_board(current_board, current_board.index(0), move)
                open_queue.put((self.get_score(new_board) + count, new_board, count+1))
        return None

board = [1,2,3,4,5,6,0,7,8]
p = Puzzle(board)
print(p.solve())

该代码实现了一个Puzzle类，其中包含了八数码问题的解题逻辑。在`__init__`方法中，我们初始化了`board`和`goal`两个列表，分别表示当前状态和目标状态。在`solve`方法中，我们使用了一个优先队列（PriorityQueue）来实现A*算法，其中优先级为当前状态与目标状态之间的距离加上到达当前状态的步数。在`get_new_board`方法中，我们根据当前状态和移动方向生成新的状态。在`get_possible_moves`方法中，我们根据当前状态计算出所有可能的移动方向。在`get_score`方法中，我们计算当前状态与目标状态之间的距离。最终，我们使用`board = [1,2,3,4,5,6,0,7,8]`初始化了一个Puzzle对象，并通过调用`solve`方法来解决八数码问题。