我一直在網上練習標準的遞回和回溯的例子，并遇到了N-queens問題（在LeetCode設定中）。 經過大量的修補，我成功地應用了遞回，以檢索給定棋盤大小n的ANY而非全部的解決方案。
然而，我的演算法在n=8之前是有效的，可以列印出有效的棋盤配置，但是當n=9或等于我所嘗試的幾個更高的數字時，則是無效的。無效的意思是，有些棋盤行充滿了點，而不是由 "Q "皇后填充的，但回溯未能捕捉到這一點，可能是由于遞回的錯誤。
例如，對于n=9，這是輸出：
測驗回溯
['Q........', '...Q......', '....Q....', '.Q.......', ' 。 .Q.....', '........Q', '.........', '.........', '.........']
測驗回溯
['...Q......', 'Q........', '...Q.....', '.Q.......', ' 。 ...Q....', '........Q', '.........', '.........', '.........']
測驗回溯
['.Q.......', '...Q.....', 'Q........', '.Q......', '. ...Q....', '........Q', '.........', '.........', '.........']
測驗回溯
['.Q.......', '...Q.....', '.....Q...', 'Q........', ' 。 .Q......', '....Q....', '......Q..', '.........', '.........']
測驗回溯
['.Q.......', '....Q....', '......Q.', '...Q.....', 'Q. .......', '...Q......', '.....Q... ', '.........', '.........']
測驗回溯
['.Q.......', '...Q.....', '.....Q...', '.......Q。', '。 .Q......', 'Q........', '......Q..', '....Q....', '.........']
測驗回溯
['.Q.......', '...Q.....', '.....Q...', '.Q......', '. ...Q....', '.........', 'Q........', '.........', '......Q... ']
測驗回溯
['.Q.......', '...Q.....', '......Q..', '...Q......', '. ......Q. ', '.....Q...', '.........', 'Q........', '....Q....']
測驗回溯
['.Q.......', '...Q.....', '.....Q...', '.Q......', '. .......Q', '.........', '....Q....', '.......Q。', 'Q........']
你可以看到，在所有情況下，棋盤中至少有一行似乎沒有被皇后填滿。
誰能給我指出下面的演算法中回溯可能失敗的地方？ 預先謝謝你！
class Solution。
def __init__(self) -> None:
self.board = ["."/span>*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:letter, i,j.
s = list(self.board[i])
s[j] = 字母
self.board[i] = ""/span>.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) 。
# 檢查它們是否在同一行。
if piece_1[0] == piece_2[0] 。
return True: 鈾?
# 檢查它們是否在同一列。
elif piece_1[1] == piece_2[1] 。
return True: 鈾?
# 檢查它們是否在同一個對角線上。
elif abs（piece_1[0] - piece_2[0] == abs(piece_1[1] - piece_2[1] )。
return True 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[/span]。
return True
def backtrack（numQueens, i, j）。
if boardOk（i,j）。
changeLetter("Q"/span>, i,j)
self.n_queens-=1
else:
return：
if self.n_queens<=0:
return 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"
測驗回溯")
# print(f" i={i}")
self.board = ["."/span>*n] * n
self.n_queens = n
self.queenPos = []
backtrack(n, i, 0) # 這對除9以外的所有情況都有效，而backtrack(n,0,i)對4以外的情況無效。
print(self.board)
if i 1<n :
i =1 :i =1 ?
else:
break else: 違反規定的行為。
return: break.
if __name__=="__main__"/span>:
n=9。
sol = Solution()
sol.solveNQueens(n)
uj5u.com熱心網友回復：
好吧，忘記我的評論。我認為對角線測驗是錯誤的，我只是認為你錯誤地應用了一個不同的想法，但你應用的想法是正確的。
你的實際問題是你沒有正確地進行回溯。你只是為每個皇后嘗試第一個位置，并且只重試放置第一個位置。backtrack需要真正地進行回溯，例如擦除它的變化：
。
def backtrack（numQueens, i, j）。
if boardOk（i,j）。
changeLetter("Q"/span>, i,j)
self.n_queens-=1
else:
return False # This is failing.
if self.n_queens == 0:
return True # 我們找到了一個解決方案。
for k in range（n）。
for l in range（n）。
if backtrack(self.n_queens, k, l):
return True # 我們找到了一個解決方案。
changeLetter(".", i, j) # 從棋盤上洗掉我們嘗試過的Q。
self.n_queens = 1。
return False # 其他皇后的嘗試都不成功
而解決方案里面的while回圈可以是一個for回圈：
self.board = ["." * n] * n # 你不需要在每個回圈中重置這些，backtrack在它后面清理了。
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")
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/319306.html
標籤：