简单易懂的八数码难题Python代码

八数码难题是一种经典的搜索问题，可以用Python实现。以下是一个简单易懂的八数码难题Python代码实现，供您参考：

# 8-puzzle solver using A* algorithm
from queue import PriorityQueue

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

    # calculate the heuristic function - Manhattan distance
    def heuristic(self):
        distance = 0
        for i in range(3):
            for j in range(3):
                value = self.board[i][j]
                if value != 0:
                    row = (value - 1) // 3
                    col = (value - 1) % 3
                    distance += abs(row - i) + abs(col - j)
        return distance

    # check if the board is solved
    def is_solved(self):
        return self.heuristic() == 0

    # generate all possible moves
    def generate_moves(self):
        moves = []
        row, col = self.find_zero()
        if row > 0:
            new_board = self.make_move(row, col, row-1, col)
            moves.append(Board(new_board, self.moves+1, self))
        if row < 2:
            new_board = self.make_move(row, col, row+1, col)
            moves.append(Board(new_board, self.moves+1, self))
        if col > 0:
            new_board = self.make_move(row, col, row, col-1)
            moves.append(Board(new_board, self.moves+1, self))
        if col < 2:
            new_board = self.make_move(row, col, row, col+1)
            moves.append(Board(new_board, self.moves+1, self))
        return moves

    # helper function to find the position of the blank space
    def find_zero(self):
        for i in range(3):
            for j in range(3):
                if self.board[i][j] == 0:
                    return i, j

    # helper function to move a tile to a new position
    def make_move(self, row1, col1, row2, col2):
        new_board = []
        for i in range(3):
            new_board.append(list(self.board[i]))
        new_board[row1][col1], new_board[row2][col2] = new_board[row2][col2], new_board[row1][col1]
        return new_board

    # print the board
    def __str__(self):
        return str(self.board)

# A* algorithm solver
def solve(initial_board):
    initial_state = Board(initial_board)
    queue = PriorityQueue()
    queue.put((initial_state.heuristic(), initial_state))
    visited_states = set()
    while not queue.empty():
        current = queue.get()
        if current.is_solved():
            return current
        visited_states.add(str(current.board))
        for move in current.generate_moves():
            if str(move.board) not in visited_states:
                queue.put((move.heuristic() + move.moves, move))
    return None

# test the solver
board = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
print(solve(board))

这个代码使用了A*算法来解决八数码难题。在Board类中，定义了每个棋盘状态的属性和方法，包括计算启发式函数，生成所有可能的移动，判断是否已经解决，以及移动一个棋子到新位置等。在solve函数中，使用了优先队列来保存待处理的状态，并且将启发式函数值和移动步数的和作为优先级。最后，调用solve函数并传入初始棋盘状态即可得到解决方案。