深度优先算法实现八数码python

深度优先算法是一种用于解决问题的搜索算法，它通过遍历问题的解空间来找到问题的解。在八数码问题中，我们需要将一个3x3的棋盘上的数字按照特定的规则进行移动，最终达到目标状态。

以下是深度优先算法实现八数码问题的Python代码示例：

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

# 定义移动方向
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# 深度优先搜索函数
def dfs(state, path):
    # 判断当前状态是否为目标状态
    if state == goal_state:
        return True

    # 获取空白格的位置
    row, col = find_blank(state)

    # 尝试移动空白格
    for direction in directions:
        new_row = row + direction[0]
        new_col = col + direction[1]

        # 判断移动是否合法
        if 0 <= new_row < 3 and 0 <= new_col < 3:
            # 复制当前状态
            new_state = [row[:] for row in state]
            # 移动空白格
            new_state[row][col], new_state[new_row][new_col] = new_state[new_row][new_col], new_state[row][col]
            # 判断新状态是否已经访问过
            if new_state not in path:
                # 添加新状态到路径中
                path.append(new_state)
                # 递归搜索
                if dfs(new_state, path):
                    return True
                # 回溯，移除当前状态
                path.pop()

    return False

# 找到空白格的位置
def find_blank(state):
    for i in range(3):
        for j in range(3):
            if state[i][j] == 0:
                return i, j

# 测试
initial_state = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
path = [initial_state]
dfs(initial_state, path)

# 输出路径
for state in path:
    print(state)