n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
条件是所有皇后不能有在同一行，同一列和同一斜线上
1.回溯算法
思路：按行枚举，维持一个列的访问列表，但是怎么判断斜线上的情况呢。一个技巧是观察斜线上行和列的规律，对于主对角线，从下到上，行一直在减少，列一直在增加，但行+列的值不变，对于负对角线，行和列都一直在增加，设置一正一负就能反映规律
2.回溯算法
也是按行枚举，其实主对角线就是相加的和一样，负对角线就是相减的差一样
class Solution: def solveNQueens(self, n: int) -> List[List[str]]: col,d,r_d=[0]*n,[0]*2*n,[0]*2*n res=[] grid=[['.']*n for _ in range(n)] def dfs(u): if u==n: res.append([ ''.join(grid[i]) for i in range(n)]) return for i in range(n): if not col[i] and not d[u+i] and not r_d[n-u+i]: col[i],d[u+i],r_d[n-u+i]=1,1,1 grid[u][i]='Q' dfs(u+1) grid[u][i]='.' col[i],d[u+i],r_d[n-u+i]=0,0,0 dfs(0) return res class Solution: def solveNQueens(self, n: int) -> List[List[str]]: res=[] s="."*n def dfs(i,tmp,col,d,r_d): if i==n: res.append(tmp) return for j in range(n): if j not in col and i+j not in d and i-j not in r_d: dfs(i+1,tmp+[s[:j]+'Q'+s[j+1:]],col|{j},d|{i+j},r_d|{i-j}) dfs(0,[],set(),set(),set()) return res
