n -queens backtrack不适用于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")