N皇后递归代码疑问：forbidden_cells两次打印结果不一致原因咨询

我尝试用递归方法解决N皇后问题，代码如下：

def solve(n,chess_arr,forbidden_cells=[]):

  print("1.",n,chess_arr,forbidden_cells)

  if n>(n*n)-len(forbidden_cells):
    return False

  elif n==1:
    printchessboard(chess_arr)
    return True

  else:
    for i in range(len(chess_arr)):
      for j in range(len(chess_arr[i])):

        print("2. ",n,(i,j),(i,j) not in forbidden_cells,forbidden_cells)

        if (i,j) not in forbidden_cells:
          chess_arr[i][j]=["Q"]
          forbidden_row=i
          forbidden_col=j
          partial_forbidden_cells=create_partial_forbidden(n,chess_arr,forbidden_row,forbidden_col,forbidden_cells)
          forbidden_cells.extend(partial_forbidden_cells)

          if solve(n-1,chess_arr,forbidden_cells):
            return True
          else:
            chess_arr[i][j]=[]
            for partial in partial_forbidden_cells:
              forbidden_cells.remove(partial)
    return False


def create_partial_forbidden(n,chess_arr,forbidden_row,forbidden_col,forbidden_cells):
  partial_forbidden_cells=[]

  ######################################### This block takes care of rows and columns #################################################
  partial_forbidden_cells.extend([(forbidden_row+i,forbidden_col )\
                          for i in range(-n,n)\
                          if (forbidden_row+i>=0 and forbidden_row+i<n and\
                          (forbidden_row+i,forbidden_col) not in forbidden_cells )])
  partial_forbidden_cells.extend([(forbidden_row,forbidden_col+i )\
                          for i in range(-n,n)\
                          if (forbidden_col+i>=0 and\
                              forbidden_col+i<n and i!=0  and\
                          (forbidden_row+i,forbidden_col) not in forbidden_cells )])
  # i!=0 ensures that the place where the queen is located is not repeated again
  ######################################### This block takes  care of the diagonals ###################################################
  partial_forbidden_cells.extend([(forbidden_row+i,forbidden_col+i)\
                          for i in range(-n,n) \
                          if (forbidden_row+i>=0 and\
                              forbidden_row+i<n and forbidden_col+i>=0 and\
                              forbidden_col+i<n and i!=0  and\
                          (forbidden_row+i,forbidden_col) not in forbidden_cells )])

  partial_forbidden_cells.extend([(forbidden_row-i,forbidden_col+i) \
                          for i in range(-n,n) \
                          if (forbidden_row-i>=0 and\
                              forbidden_row-i<n and forbidden_col+i>=0 and\
                              forbidden_col+i<n and i!=0  and\
                          (forbidden_row+i,forbidden_col) not in forbidden_cells )])
  # i!=0 ensures that the place where the queen is located is not repeated again
  #####################################################################################################################################

  #print("forbidden cells are ", forbidden_cells)
  return partial_forbidden_cells

疑问与预期 #

第一个print语句（标记为1.）多次输出非空的forbidden_cells列表，但第二个print语句（标记为2.）输出的该列表始终为空，我不清楚原因。

我的预期是：由于将forbidden_cells作为参数传递，它应在每次迭代中更新，且每次迭代都能使用最新的列表。

典型输出 #

1. 3 [[['Q'], [], [], []], [[], [], [], []], [[], [], [], []], [[], [], [], []]] [(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (0, 2), (0, 3), (1, 1), (2, 2), (3, 3)]
2.  4 (0, 1) True []

问题原因分析 #

1. 调用层级差异：从输出能明显看到，print 1.对应的是n=3的递归调用层级，而print 2.对应的是n=4的上层调用层级。在n=4的层级中，你还没进入if (i,j) not in forbidden_cells的分支，尚未执行forbidden_cells.extend(partial_forbidden_cells)操作，此时这个层级的forbidden_cells自然是空的；而n=3的层级是递归进入的下一层，已经被上层代码执行过extend，所以列表有值。

2. 默认参数的陷阱：函数定义def solve(n,chess_arr,forbidden_cells=[])存在严重问题——Python中可变默认参数（比如列表）的初始化只会在函数定义时执行一次，所有不传递forbidden_cells参数的调用都会共享同一个列表实例。这会导致递归回溯时的状态混乱，是后续可能遇到更多问题的根源。

修复建议 #

把默认参数改为None，并在函数内部初始化新列表，避免共享实例：

def solve(n, chess_arr, forbidden_cells=None):
    # 初始化空列表，避免共享默认参数实例
    if forbidden_cells is None:
        forbidden_cells = []
    # 后续代码保持不变

另外，create_partial_forbidden函数里的列表推导式存在逻辑错误：比如判断条件里写的是(forbidden_row+i,forbidden_col) not in forbidden_cells，但实际应该判断当前生成的坐标（比如(forbidden_row,forbidden_col+i)）是否在禁止列表中，这会导致生成的禁止单元格不准确，需要修正这些条件。

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