N皇后问题：bt变量为何无故发生值变更？

代码实现 #

def poss_move(val, board, n):
  # val is a value between 0 and n*n-1
  for i in range(n*n):
    if i == val:
      board[i // n][i % n] = 'Q'
      continue
    if i % n == val % n or i // n == val // n: #mark row and column with a dot
      board[i//n][i%n] = '.'

    #mark diagonals with a dot
    if i % (n + 1) == val % (n + 1) and abs(i % n - val % n) == abs(i // n - val // n): 
      board[i//n][i%n] = '.'
    if i % (n - 1) == val % (n - 1) and abs(i % n - val % n) == abs(i // n - val // n):
      board[i//n][i%n] = '.'
  return board

def next_available_position(val, board, n):
  if val < 0 or val >= n * n:
    return -1
  for i in range(val, n * n):
    if board[i//n][i%n] == '0':
      return i
  return -1

def sol(val, board, bt, result, n):
  board[val // n][val % n] == 'Q'
  print(f'AW1 val: {val}, bt: {bt}')
  board = poss_move(val=val, board=board, n=n)
  print(f'AW2 val: {val}, bt: {bt}')
  nap = next_available_position(val=val, board=board, n=n)
  while nap >= 0:
    board_tmp = [i for i in board]
    result, board_tmp = sol(val=nap, board=board, bt=board_tmp, result=result, n=n)
    board = [i for i in board_tmp]
    board[nap // n][nap % n] = '.'
    nap = next_available_position(val=nap, board=board, n=n)
  result.append([board,2])
  return result, bt

def run():
  m = 3 #board size = n x n
  board_ini = [['0' for x in range(m)] for y in range(m)] #initialize board with '0' in every row and col
  result = []
  board_t = []
  result, board_t = sol(val=0, board=board_ini, bt=board_t, result=result, n=m)

run()

运行输出 #

AW1 val: 0, bt: []
AW2 val: 0, bt: []
AW1 val: 5, bt: [['Q', '.', '.'], ['.', '.', '0'], ['.', '0', '.']]
AW2 val: 5, bt: [['Q', '.', '.'], ['.', '.', 'Q'], ['.', '.', '.']]

问题 #

为什么bt变量的值会从AW1打印的内容变为AW2打印的内容？我原本以为是全局变量导致的问题，因此重写代码规避全局变量，我认为bt是局部变量，且在两次打印之间未对其执行任何操作，但它的值却发生了变更。

原因分析 #

核心问题出在Python列表的浅拷贝特性上：

• 当你执行board_tmp = [i for i in board]时，这只是做了浅拷贝——外层列表是新的，但里面的每个子列表（比如['Q', '.', '.']）仍然是原board中子列表的引用。
• 在递归调用sol(val=nap, board=board, bt=board_tmp, ...)时，bt接收的board_tmp里的子列表和当前board的子列表指向同一个内存对象。
• 随后调用poss_move函数时，会直接修改board中的子列表元素（比如把位置5设为Q，相关行列和对角线设为.）。因为bt的子列表和board的子列表是同一个对象，所以这些修改会同步反映到bt中，导致AW1和AW2打印的bt内容出现差异。

解决方法 #

要避免这种引用共享的问题，需要对board做深拷贝，确保所有层级的列表都是新对象：

1. 先导入copy模块：import copy
2. 将board_tmp = [i for i in board]替换为：

   board_tmp = copy.deepcopy(board)
   

这样board_tmp和原board完全独立，后续修改board不会影响bt的值。

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