51. N-Queens
https://leetcode.cn/problems/n-queens/
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
class Solution: def is_valid(self, path, x, y): """ 给出现有的棋盘path,和位置(x,y),判断在(x,y)处放置棋子是否会有冲突 """ for i in range(x): if path[i][y] == "Q": return False for j in range(y): if path[x][j] == "Q": return False # i == j i, j = x - 1, y - 1 while i >= 0 and j >= 0: if path[i][j] == "Q": return False i -= 1 j -= 1 # i + j = k i, j = x - 1, y + 1 while i >= 0 and j < self.n: if path[i][j] == "Q": return False i -= 1 j += 1 return True def dfs(self, path, idx): """ 尝试在第idx行放置皇后 """ if idx == self.n: tmp = list( map(lambda x: "".join(x), path) ) # 将当前棋盘path的每一行字符数组,拼接成字符串 self.res.append(tmp) return for j in range(self.n): if self.is_valid(path, idx, j) == False: continue path[idx][j] = "Q" self.dfs(path, idx+1) # 恢复现场 restore path[idx][j] = "." def solveNQueens(self, n: int) -> List[List[str]]: self.n = n path = [ ["."]*n for _ in range(n)] self.res = [] idx = 0 self.dfs(path, idx) return self.resView Code
52. N皇后 II
https://leetcode.cn/problems/n-queens-ii/
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
class Solution: def is_valid(self, path, x, y): for i in range(x): if path[i][y] == "Q": return False for j in range(y): if path[x][j] == "Q": return False i, j = x-1, y-1 while i >= 0 and j >= 0: if path[i][j] == "Q": return False i -= 1 j -= 1 i, j = x - 1, y + 1 while i >= 0 and j < self.n: if path[i][j] == "Q": return False i -= 1 j += 1 return True def dfs(self, path, idx): if idx == self.n: self.cnt += 1 return for j in range(self.n): if self.is_valid(path, idx, j) == False: continue path[idx][j] = "Q" self.dfs(path, idx+1) path[idx][j] = "." def totalNQueens(self, n: int) -> int: self.n = n self.cnt = 0 path = [["."]*n for _ in range(n)] self.dfs(path, 0) return self.cntView Code
标签:False,idx,self,return,range,path,Queens From: https://www.cnblogs.com/zijidan/p/16882528.html