N 皇后回溯不适用于 n=9 及更高版本

Question

我一直在网上练习标准回避和回溯示例，遇到了 N 皇后问题（在 LeetCode 设置中）。经过大量修改后，我设法应用递归来检索给定板尺寸 n 的任何（不是全部）解决方案。

然而，我的算法工作到 n=8，打印出有效的电路板配置，但当 n=9 或等于我尝试过的几个更高的数字时，打印出无效的电路板配置。无效意味着某些板行充满了点并且没有填充“Q”皇后，但回溯未能捕捉到这一点，可能是由于错误的递归。

例如，对于 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)

Answer 1

好的，忘记我的评论。我以为对角线测试是错误的，我只是认为你错误地应用了不同的想法，但你应用的想法是正确的。

你的实际问题是你没有正确回溯：你只是为每个皇后尝试第一个位置，并且只重试放置第一个。 backtrack 需要实际回溯，例如删除它的更改：


        def backtrack(numQueens, i, j):
          
          if boardOk(i,j):
              changeLetter("Q", i,j)
              self.n_queens-=1
          else:
            return False # This is failing
          
          if self.n_queens == 0:
            return True # We found a solution
                    
          for k in range(n):
            for l in range(n):
              if backtrack(self.n_queens, k, l):
                  return True # We found a solution
          changeLetter(".", i, j) # Remove the Queen we tried from the board.
          self.n_queens += 1
          return False # None of the tries for other Queens works

解决方案中的 while 循环可以是 for 循环：

        self.board =  ["." * n] * n # You don't need to reset these each loop. backtrack cleans up behind it.
        self.n_queens = n
        self.queenPos = []
        for i in range(n):
          if backtrack(n, i, 0):
            print(self.board)
            return self.board
        else:
            raise ValueError("We did not find a solution")

N 皇后回溯不适用于 n=9 及更高版本

N-queens backtrack not working for n=9 and higher

python

recursion

backtracking

n-queens