N-queens回溯不适用于n=9及更高版本

Question

我一直在网上练习标准的递归和回溯示例，遇到了N-queens问题(在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")