N数码问题IDDFS算法move函数异常修改前序状态如何解决？

该问题的核心是Python可变对象的引用传递特性：

• 你传入move函数的state中的grid是二维列表，属于可变对象，函数内拿到的是原列表的内存引用，没有做拷贝
• 当前move函数的逻辑是直接在原grid上做元素交换，yield出去的next_state里的grid和原state的grid指向同一块内存，即便后续回溯时把元素交换回来，之前已经存入路径的state的grid内容也会被同步修改，最终导致状态错乱

另外还有一个隐藏bug：move_blank函数用了elif做方向判断，只会返回第一个符合条件的移动方向，无法生成所有合法的下一步状态。

1. 修复方向生成逻辑 #

把move_blank中的elif全部替换为独立的if判断，保证所有合法移动方向都能被生成：

def move_blank(i, j, n):
    if i + 1 < n:
        yield i + 1, j
    if i - 1 >= 0:
        yield i - 1, j
    if j + 1 < n:
        yield i, j + 1
    if j - 1 >= 0:
        yield i, j - 1

2. 修复原状态被修改的问题 #

在move函数生成下一步状态时，对grid做深拷贝，保证原grid不会被改动，yield出去的新状态用独立的grid对象：

def move(state):
    i, j, grid = state
    n = len(grid)
    for pos in move_blank(i, j, n):
        i1, j1 = pos
        # 临时交换原grid得到下一步布局
        grid[i][j], grid[i1][j1] = grid[i1][j1], grid[i][j]
        # 拷贝生成新的grid对象，和原grid完全独立
        new_grid = [row.copy() for row in grid]
        # 恢复原grid的内容，保证原状态不变
        grid[i][j], grid[i1][j1] = grid[i1][j1], grid[i][j]
        # 返回携带新grid的状态
        yield [i1, j1, new_grid]

你当前实现的是普通递归DFS，不是迭代加深IDDFS，若要改成IDDFS需要额外增加深度限制参数，每次迭代提升深度上限，避免无限递归或者在深层无效路径上浪费算力。

内容的提问来源于stack exchange，提问作者user13413898