DFS求解八数码问题的代码，包含输出路径

下面是使用深度优先搜索（DFS）算法求解八数码问题的 Python 代码，其中包含输出路径的实现。

# 八数码问题的状态表示为一个 3x3 的矩阵
# 0 表示空格

# 初始状态
start_state = [
    [2, 8, 3],
    [1, 0, 4],
    [7, 6, 5]
]

# 目标状态
goal_state = [
    [1, 2, 3],
    [8, 0, 4],
    [7, 6, 5]
]

# 方向数组，上下左右
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dirs = ['u', 'd', 'l', 'r']

# 记录路径
path = []

# 深度优先搜索
def dfs(state, depth):
    # 已达到最大深度
    if depth == 0:
        return False
    
    # 判断是否达到目标状态
    if state == goal_state:
        return True
    
    # 遍历空格周围的四个方向
    for i in range(4):
        nx = -1
        ny = -1
        
        # 找到空格的坐标
        for x in range(3):
            for y in range(3):
                if state[x][y] == 0:
                    nx = x + dx[i]
                    ny = y + dy[i]
                    break
            if nx != -1:
                break
        
        # 判断是否越界
        if nx < 0 or nx >= 3 or ny < 0 or ny >= 3:
            continue
        
        # 交换空格和相邻的数字
        new_state = [row[:] for row in state]
        new_state[nx][ny], new_state[x][y] = new_state[x][y], new_state[nx][ny]
        
        # 判断是否已经访问过
        if new_state in vis:
            continue
        
        # 标记已经访问
        vis.add(tuple(map(tuple, new_state)))
        
        # 记录路径
        path.append(dirs[i])
        
        # 递归搜索下一层状态
        if dfs(new_state, depth - 1):
            return True
        
        # 恢复路径
        path.pop()
    
    return False

# 初始化已访问状态集合，将初始状态加入其中
vis = set()
vis.add(tuple(map(tuple, start_state)))

# 从初始状态开始搜索，最大深度为 30
dfs(start_state, 30)

# 输出路径
print(' -> '.join(path))

该代码使用了一个已访问状态集合 `vis` 来避免重复访问状态，同时记录路径的方法是在 `dfs` 函数中的递归调用前后分别添加和删除当前方向字符，最后将整个路径连接起来输出。