解决八数码难题的Python代码

八数码难题是一种经典的人工智能问题，可以使用搜索算法来解决。以下是一个使用A*算法来解决八数码难题的Python代码实现：

import heapq

# 定义状态类
class State:
    def __init__(self, board, moves, manhattan):
        self.board = board # 当前状态的棋盘
        self.moves = moves # 当前状态的步数
        self.manhattan = manhattan # 当前状态的曼哈顿距离

    # 定义小于号操作符，用于堆排序
    def __lt__(self, other):
        return (self.moves + self.manhattan) < (other.moves + other.manhattan)

# 定义曼哈顿距离函数
def manhattan(board):
    distance = 0
    for i in range(3):
        for j in range(3):
            if board[i][j] != 0:
                row = (board[i][j] - 1) // 3
                col = (board[i][j] - 1) % 3
                distance += abs(row - i) + abs(col - j)
    return distance

# 定义状态转移函数
def move(board, i1, j1, i2, j2):
    new_board = []
    for i in range(3):
        row = []
        for j in range(3):
            row.append(board[i][j])
        new_board.append(row)
    new_board[i1][j1], new_board[i2][j2] = new_board[i2][j2], new_board[i1][j1]
    return new_board

# 定义A*算法求解函数
def solve(initial_board):
    heap = []
    heapq.heappush(heap, State(initial_board, 0, manhattan(initial_board)))
    while heap:
        state = heapq.heappop(heap)
        if state.board == [[1, 2, 3], [4, 5, 6], [7, 8, 0]]:
            return state.moves
        i, j = next((i, j) for i in range(3) for j in range(3) if state.board[i][j] == 0)
        for i2, j2 in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):
            if 0 <= i2 < 3 and 0 <= j2 < 3:
                new_board = move(state.board, i, j, i2, j2)
                heapq.heappush(heap, State(new_board, state.moves+1, manhattan(new_board)))
    return None

# 示例
initial_board = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
print(solve(initial_board))