N皇后回溯算法n≥9时输出无效棋盘，求代码bug定位

问题描述 #

我在练习标准递归与回溯算法时，在LeetCode平台练习N皇后问题，实现了查找任意一个解而非全部解的递归逻辑。该算法在n≤8时可输出合法棋盘配置，但n=9及以上时返回无效结果：部分行未放置皇后Q，仅为全点行，回溯逻辑未捕获该异常，推测递归存在bug。

n=9时输出样例如下：

testing backtrack
['Q........', '..Q......', '....Q....', '.Q.......', '...Q.....', '........Q', '.........', '.........', '.........']

testing backtrack
['..Q......', 'Q........', '...Q.....', '.Q.......', '....Q....', '........Q', '.........', '.........', '.........']

testing backtrack
['.Q.......', '...Q.....', 'Q........', '..Q......', '....Q....', '........Q', '.........', '.........', '.........']

testing backtrack
['.Q.......', '...Q.....', '.....Q...', 'Q........', '..Q......', '....Q....', '......Q..', '.........', '.........']

testing backtrack
['.Q.......', '....Q....', '......Q..', '...Q.....', 'Q........', '..Q......', '.....Q...', '.........', '.........']

testing backtrack
['.Q.......', '...Q.....', '.....Q...', '.......Q.', '..Q......', 'Q........', '......Q..', '....Q....', '.........']

testing backtrack
['.Q.......', '...Q.....', '.....Q...', '..Q......', '....Q....', '.........', 'Q........', '.........', '......Q..']

testing backtrack
['.Q.......', '...Q.....', '......Q..', '..Q......', '.......Q.', '.....Q...', '.........', 'Q........', '....Q....']

testing backtrack
['.Q.......', '...Q.....', '.....Q...', '..Q......', '........Q', '.........', '....Q....', '.......Q.', 'Q........']

所有输出结果中均至少存在一行未放置皇后的行。

问题代码 #

class Solution:
  def __init__(self) -> None:
    self.board =  ["."*n] * n
    self.n_queens = n    
    self.queenPos = []

  def solveNQueens(self, n: int) -> list[list[str]]:

    def changeLetter(letter, i,j):
      # change letter in board
      s = list(self.board[i])
      s[j] = letter
      self.board[i] = "".join(s)
      if letter == "Q":
        self.queenPos.append([i,j])
      else:
        self.queenPos.pop()

    def boardOk(k,l):
      # print(self.queenPos)
      def check_attack(piece_1, piece_2):
        # check if they are in the same row
        if piece_1[0] == piece_2[0]:
            return True
        # check if they are in the same column
        elif piece_1[1] == piece_2[1]:
            return True
        # check if they are in the same diagonal
        elif abs(piece_1[0] - piece_2[0]) == abs(piece_1[1] - piece_2[1]):
            return True
        else:
            # print("queens are not attacking in diagonal")
            return False
      
      if len(self.queenPos)>0:
        # print(self.queenPos)
        for pos in self.queenPos:
          if check_attack([k,l], pos):
            return False

      return True

    def backtrack(numQueens, i, j):
      
      if boardOk(i,j):
          changeLetter("Q", i,j)
          self.n_queens-=1
      else:
        return
      
      if self.n_queens<=0:
        return
                
      for k in range(n):
        for l in range(n):
          backtrack(self.n_queens, k, l)
      
    i=0
    while self.n_queens!=0:
      print(f"\ntesting backtrack")
      # print(f"\ti={i}")
      self.board =  ["."*n] * n
      self.n_queens = n
      self.queenPos = []
      backtrack(n, i, 0) # this works for all cases except 9 instead of backtrack(n,0,i) which doesn't except for 4
      print(self.board)
      if i+1<n :
        i+=1 
      else:
        break  

    return

if __name__=="__main__":
    n=9
    sol = Solution()
    sol.solveNQueens(n)

bug定位与修复建议 #

核心错误点： #

• 缺少回溯撤销操作：backtrack函数中放置皇后后，如果后续递归找不到合法位置，没有把当前放置的皇后撤销（没有调用changeLetter把Q改回.，也没有把self.n_queens计数加回），一旦某条递归路径走死，就会停在当前状态，剩下的皇后无合法位置可放，自然出现全点行。
• 递归遍历逻辑错误：遍历棋盘用了两层for循环，k和l都从0开始，会重复遍历已经放过皇后的行，不仅效率极低，还会导致递归路径混乱。标准N皇后回溯逻辑都是按行遍历，每行仅放一个皇后，天然避免行冲突，完全不需要两层循环遍历所有格子。
• 语法错误：原代码中abs(piece_1[0] - piece_2[0]) == abs(piece_1[1] - piece_2[1]缺少右括号，运行会直接报错。
• 初始化不规范：["."*n] * n生成的列表所有元素都是同一个字符串的引用，虽然你后续修改时先转成了列表再赋值不会触发这个问题，但更稳妥的写法是["."*n for _ in range(n)]。

修复思路： #

1. 回溯函数按行递归，每次处理第row行，遍历该行所有列查找合法位置放置皇后
2. 放置皇后后递归处理下一行，递归返回后立刻撤销当前皇后的放置
3. 只要找到一个合法解就直接返回，不需要继续遍历剩余分支

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