51. N 皇后
难度困难569收藏分享切换为英文关注反馈
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例：
输入：4 输出：[ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。
提示：
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。 class Solution: def solveNQueens(self, n: int) -> List[List[str]]: pan = [0]*(n+1) res = [] def dfs(cur, n): flag = 0 if cur==n+1: tmp = [""]*n for i in range(1,n+1): for j in range(1,n+1): if j!=pan[i]: tmp[i-1] += '.' else: tmp[i-1] += 'Q' res.append(tmp) return for i in range(1,n+1): pan[cur]=i #数组的下标表示行，对应的值表示列 flag = 1 for j in range(1,cur): #检测当前皇后的位置和之前的cur-1个皇后的位置是否冲突 if pan[j]==i or (abs(cur-j)==abs(pan[j]-i)): flag = 0 break if flag: dfs(cur+1, n) dfs(1, n) return res
