八数码问题a*算法python

以下是一个使用A*算法解决八数码问题的Python实现：

from queue import PriorityQueue

class Board:
    def __init__(self, board):
        self.board = board
        self.zero_pos = self.get_zero_pos()
        self.g = 0
        self.h = self.get_h()

    def __lt__(self, other):
        return self.g + self.h < other.g + other.h

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

    def __str__(self):
        return '\n'.join(' '.join(str(x) for x in row) for row in self.board)

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

    def get_h(self):
        h = 0
        for i in range(3):
            for j in range(3):
                if self.board[i][j] != 0:
                    x, y = divmod(self.board[i][j]-1, 3)
                    h += abs(x-i) + abs(y-j)
        return h

    def get_neighbours(self):
        neighbours = []
        i, j = self.zero_pos
        if i > 0:
            neighbour = [row[:] for row in self.board]
            neighbour[i][j], neighbour[i-1][j] = neighbour[i-1][j], neighbour[i][j]
            neighbours.append(Board(neighbour))
        if i < 2:
            neighbour = [row[:] for row in self.board]
            neighbour[i][j], neighbour[i+1][j] = neighbour[i+1][j], neighbour[i][j]
            neighbours.append(Board(neighbour))
        if j > 0:
            neighbour = [row[:] for row in self.board]
            neighbour[i][j], neighbour[i][j-1] = neighbour[i][j-1], neighbour[i][j]
            neighbours.append(Board(neighbour))
        if j < 2:
            neighbour = [row[:] for row in self.board]
            neighbour[i][j], neighbour[i][j+1] = neighbour[i][j+1], neighbour[i][j]
            neighbours.append(Board(neighbour))
        return neighbours

def solve_puzzle(start_board):
    start_node = Board(start_board)
    end_board = [[1,2,3],[4,5,6],[7,8,0]]
    end_node = Board(end_board)
    visited = set()
    queue = PriorityQueue()
    queue.put(start_node)
    while not queue.empty():
        node = queue.get()
        if node.board == end_node.board:
            return node.g
        visited.add(node)
        for neighbour in node.get_neighbours():
            if neighbour not in visited:
                neighbour.g = node.g + 1
                queue.put(neighbour)
    return -1

if __name__ == '__main__':
    board = [[1,2,3],[4,5,6],[7,0,8]]
    moves = solve_puzzle(board)
    if moves == -1:
        print('Unsolvable puzzle.')
    else:
        print('Number of moves required:', moves)

该实现使用了一个`Board`类来表示八数码问题中的一个棋盘状态。该类包含了棋盘状态、空格位置、g值（从起始状态到该状态的距离）和h值（该状态到目标状态的估计距离）等信息。

在`solve_puzzle`函数中，我们使用了一个优先队列来存储待搜索的状态。每次从队列中取出g+h最小的状态进行搜索。如果该状态是目标状态，则返回该状态的g值作为答案。如果搜索完所有状态都没有找到目标状态，则返回-1表示该八数码问题无解。

该实现的时间复杂度为O(b^d)，其中b是每个状态的平均分支因子，d是目标状态的深度。在八数码问题中，b的值大约为2.5，d的最大值为31，因此该算法的时间复杂度为O(2.5^31)，是可以接受的。