Leetcode Link: 51. N 皇后 - 力扣（LeetCode）
题目
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
国际象棋中皇后能够攻击的位置
皇后能够攻击同一行、同一列、同一斜线(X)上的所有的棋子
解法一
思路：属于回溯问题中的棋盘问题，收集的是满足条件的叶子节点。
满足题目条件 能够走到叶子节点就可以满足条件（不满足问题条件会被剪枝）
剪枝条件 当前位置放置皇后同一行有其他皇后 同一列有其他皇后 正斜线上有其他皇后 反斜线上有其他皇后
停止回溯条件 走到叶子节点就可以停止了 若不满足防止皇后条件，是 continue 而不是 return
剪枝条件判定简化
在实际代码中，我们逐行放置皇后，这样的话可以对剪枝判定做出如下简化 1) 逐行放置的话就不用判定同行了 2) 由于是从上到下逐行放置，所以只需要判定本行往上的列（往下的还没放呢），放置点左上、右上方向有没有其他皇后
题解：
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def backtracking(i):
# 放置第i行的皇后
nonlocal checkboard, res
# 满足题目要求，停止回溯
if i == self.n:
res.append(checkboard.copy())
return
# 遍历当前的每一列
for j in range(self.n):
# 准备位置[i,j]放个皇后，不满足放置条件则跳过
# 注意这里都还没改变 checkboard 呢，满足条件再改
if not self.check(checkboard, i, j):
continue
checkboard[i] = checkboard[i][:j]+'Q'+checkboard[i][j+1:]
backtracking(i+1)
checkboard[i] = checkboard[i][:j]+'.'+checkboard[i][j+1:]
self.n = n
res = []
checkboard = ['.'*n for _ in range(self.n)]
backtracking(0)
return res
# 判定当前放置点是否合格
def check(self, checkboard, i, j):
### 同一列上有Q (只往上看)
row = i
while(1):
row -= 1
if row < 0: break
if checkboard[row][j] == 'Q':
return False
### 左上对角线有Q:
row = i
col = j
while(1):
row -= 1
col -= 1
if row < 0 or col <0:
break
if checkboard[row][col] == 'Q':
return False
### 右上对角线有Q:
row = i
col = j
while(1):
row -= 1
col += 1
if row < 0 or col > self.n-1:
break
if checkboard[row][col] == 'Q':
return False
return True复习时的代码
利用一个set()来指示哪些col还可以用，不用每次都遍历了。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
path = ["".join(['.']*n) for _ in range(n)]
valid_col = set([i for i in range(n)])
def process(i):
nonlocal valid_col
if i == n:
res.append(path.copy())
for j in range(n):
if j not in valid_col: continue
if self.check_diag(i,j,path):
valid_col.remove(j)
path[i] = path[i][:j]+'Q'+path[i][j+1:]
process(i+1)
path[i] = path[i][:j]+'.'+path[i][j+1:]
valid_col.add(j)
process(0)
return res
# 对角线检查
def check_diag(self, i, j, path):
bkp_i = i
bkp_j = j
while(i>=0 and j>=0):
if path[i][j] == 'Q':
return False
else:
i -= 1
j -= 1
i = bkp_i
j = bkp_j
while(i>=0 and j<len(path[0])):
if path[i][j] == 'Q':
return False
else:
i -= 1
j += 1
return True
启发和联系
- 由于字符串在 python 中是不可变变量，因此每一行放置/删除皇后的的语句相当于重新赋值
# 放置皇后
checkboard[i] = checkboard[i][:j]+'Q'+checkboard[i][j+1:]
# 删除皇后
checkboard[i] = checkboard[i][:j]+'.'+checkboard[i][j+1:]- 注意初始棋盘格的创建方式
checkboard = ['.'*n for _ in range(self.n)]实际上利用了 'a'*3=='aaa'，类似[0]*3==[0,0,0]