为什么我的 N Queens 算法到达最后一行?
Why is my N Queens algorithm reaching the last row?
我想我理解了 NQueens 算法的要点 - 你检查每一行的可用空间,如果它们存在,就把一个皇后放在那里,然后递归地调用算法到下一行。这是我的算法(N 大小为 3)
from typing import List
import pdb
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
self.solutions = 0
self.attack_zone = [[0]*n for i in range(n)]
self.size = n
self.backtrack_nqueens(0,0) #start on row 0
return self.solutions
def backtrack_nqueens(self,row,iteration):
#starting at row
for col in range(self.size):
if self.is_not_under_attack(row,col):
print("on iteration",iteration,row,col,"was a safe place for some reason")
#adds queen to this row
self.place_or_remove_queen(row,col,True)
if row + 1 == self.size:
## THIS SHOULD NEVER HAPPEN
self.solutions += 1
else:
self.backtrack_nqueens(row+1,iteration+1)
#removes queen from this row
self.place_or_remove_queen(row,col,False)
def place_or_remove_queen(self,row,col,place):
flag = 1 if place else 0
self.attack_zone[row] = [flag]*self.size
#for col
for r in range(self.size):
self.attack_zone[r][col] = flag
#lower right
for r,c in zip(range(row,self.size,1),range(col,self.size,1)):
self.attack_zone[r][c] = flag
#upper right
for r,c in zip(range(row,-1,-1),range(col,self.size,1)):
self.attack_zone[r][c] = flag
#lower left
for r,c in zip(range(row,self.size,1),range(col,-1,-1)):
self.attack_zone[r][c] = flag
#upper left
for r,c in zip(range(row,-1,-1),range(col,-1,-1)):
self.attack_zone[r][c] = flag
def is_not_under_attack(self,row,col):
return self.attack_zone[row][col] == 0
s = Solution()
print(s.solveNQueens(3))
当我 运行 这样做时,self.solutions 以 3 结束 - 基本上它为女王找到了 3 个位置,我们都知道这不应该发生。我不明白它是怎么走到我说##这永远不应该发生的那一行的。
我唯一能想到的是,我正在以某种方式删除不应该删除的女王?所以我的 attack_zone 在不应该有空格的时候有空格。有人可以指出我在导致这种情况的递归中做错了什么以及为什么吗?
问题是,当你移除一个皇后时,你将相应的方格标记为 "free",即将它们的 "threat count" 设置为零,而不管另一个皇后是否也威胁到该方格。考虑到您的示例,会发生以下情况:
# Iteration 1 # Iteration 2 # Iteration 3
| 1 | 1 | Q | | 1 | 1 | Q | | 0 | 0 | Q |
+---+---+---+ +---+---+---+ +---+---+---+
| 0 | 1 | 1 | | Q | 1 | 1 | | 0 | 0 | 0 |
+---+---+---+ +---+---+---+ +---+---+---+
| 1 | 0 | 1 | | 1 | 1 | 1 | | 0 | 0 | 1 |
在第 3 次迭代中,(1, 0)
上的皇后被移除,所有相应的方块都被标记为 0
,也包括那些实际上受到 (0, 2)
上皇后威胁的方块。 (1, 1)
和 (1, 2)
上的皇后也是如此,后者最终导致最后一行 (2, 0)
上的自由方块。
为了使算法正常工作,您可以维护一个 "threat count" 来跟踪一个方格中有多少皇后受到威胁。放置皇后会使计数增加一,移除皇后会使计数减少一。您可以通过将 flag
的值更改为 flag = 1 if place else -1
然后在所有地方使用 self.attack_zone[r][c] += flag
而不是 self.attack_zone[r][c] = flag
来实现这一点。这给出了下图:
# Iteration 1 # Iteration 2 # Iteration 3
| 1 | 1 | Q | | 2 | 2 | Q | | 1 | 1 | Q |
+---+---+---+ +---+---+---+ +---+---+---+
| 0 | 1 | 1 | | Q | 2 | 2 | | 0 | 1 | 1 |
+---+---+---+ +---+---+---+ +---+---+---+
| 1 | 0 | 1 | | 2 | 1 | 1 | | 1 | 0 | 1 |
我想我理解了 NQueens 算法的要点 - 你检查每一行的可用空间,如果它们存在,就把一个皇后放在那里,然后递归地调用算法到下一行。这是我的算法(N 大小为 3)
from typing import List
import pdb
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
self.solutions = 0
self.attack_zone = [[0]*n for i in range(n)]
self.size = n
self.backtrack_nqueens(0,0) #start on row 0
return self.solutions
def backtrack_nqueens(self,row,iteration):
#starting at row
for col in range(self.size):
if self.is_not_under_attack(row,col):
print("on iteration",iteration,row,col,"was a safe place for some reason")
#adds queen to this row
self.place_or_remove_queen(row,col,True)
if row + 1 == self.size:
## THIS SHOULD NEVER HAPPEN
self.solutions += 1
else:
self.backtrack_nqueens(row+1,iteration+1)
#removes queen from this row
self.place_or_remove_queen(row,col,False)
def place_or_remove_queen(self,row,col,place):
flag = 1 if place else 0
self.attack_zone[row] = [flag]*self.size
#for col
for r in range(self.size):
self.attack_zone[r][col] = flag
#lower right
for r,c in zip(range(row,self.size,1),range(col,self.size,1)):
self.attack_zone[r][c] = flag
#upper right
for r,c in zip(range(row,-1,-1),range(col,self.size,1)):
self.attack_zone[r][c] = flag
#lower left
for r,c in zip(range(row,self.size,1),range(col,-1,-1)):
self.attack_zone[r][c] = flag
#upper left
for r,c in zip(range(row,-1,-1),range(col,-1,-1)):
self.attack_zone[r][c] = flag
def is_not_under_attack(self,row,col):
return self.attack_zone[row][col] == 0
s = Solution()
print(s.solveNQueens(3))
当我 运行 这样做时,self.solutions 以 3 结束 - 基本上它为女王找到了 3 个位置,我们都知道这不应该发生。我不明白它是怎么走到我说##这永远不应该发生的那一行的。
我唯一能想到的是,我正在以某种方式删除不应该删除的女王?所以我的 attack_zone 在不应该有空格的时候有空格。有人可以指出我在导致这种情况的递归中做错了什么以及为什么吗?
问题是,当你移除一个皇后时,你将相应的方格标记为 "free",即将它们的 "threat count" 设置为零,而不管另一个皇后是否也威胁到该方格。考虑到您的示例,会发生以下情况:
# Iteration 1 # Iteration 2 # Iteration 3
| 1 | 1 | Q | | 1 | 1 | Q | | 0 | 0 | Q |
+---+---+---+ +---+---+---+ +---+---+---+
| 0 | 1 | 1 | | Q | 1 | 1 | | 0 | 0 | 0 |
+---+---+---+ +---+---+---+ +---+---+---+
| 1 | 0 | 1 | | 1 | 1 | 1 | | 0 | 0 | 1 |
在第 3 次迭代中,(1, 0)
上的皇后被移除,所有相应的方块都被标记为 0
,也包括那些实际上受到 (0, 2)
上皇后威胁的方块。 (1, 1)
和 (1, 2)
上的皇后也是如此,后者最终导致最后一行 (2, 0)
上的自由方块。
为了使算法正常工作,您可以维护一个 "threat count" 来跟踪一个方格中有多少皇后受到威胁。放置皇后会使计数增加一,移除皇后会使计数减少一。您可以通过将 flag
的值更改为 flag = 1 if place else -1
然后在所有地方使用 self.attack_zone[r][c] += flag
而不是 self.attack_zone[r][c] = flag
来实现这一点。这给出了下图:
# Iteration 1 # Iteration 2 # Iteration 3
| 1 | 1 | Q | | 2 | 2 | Q | | 1 | 1 | Q |
+---+---+---+ +---+---+---+ +---+---+---+
| 0 | 1 | 1 | | Q | 2 | 2 | | 0 | 1 | 1 |
+---+---+---+ +---+---+---+ +---+---+---+
| 1 | 0 | 1 | | 2 | 1 | 1 | | 1 | 0 | 1 |