我想我理解了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个位置,我们都知道这是不应该发生的。我不明白这场争吵怎么会演变成我说“这永远不会发生”的那一排
我能想到的唯一一件事是,我不知何故要除掉一个不该被除掉的女王?所以我的攻击区在不应该的时候有空位。有人能指出我在递归中做错了什么会导致这种情况吗?为什么
问题是,当你移除一个女王时,你会将相应的方块标记为“自由”,即将其“威胁计数”设置为零,而不管另一个女王是否也威胁该方块。考虑到您的示例,会发生以下情况:
在迭代#3中
(1, 0)
上的皇后被移除,所有相应的方块被标记为0
,也就是实际上受到(0, 2)
上皇后威胁的方块。同样的情况也发生在(1, 1)
和(1, 2)
上的皇后区,后者最终导致最后一行(2, 0)
上的自由正方形为了使算法工作,您可以维护一个“威胁计数”,它跟踪一个正方形受到威胁的皇后数量。放置皇后会增加一个,移除皇后会减少一个。您可以通过将
flag
的值更改为flag = 1 if place else -1
,然后在任何地方使用self.attack_zone[r][c] += flag
而不是self.attack_zone[r][c] = flag
来实现这一点。这就给出了以下图片:相关问题 更多 >
编程相关推荐