N 皇后
N-Queens
本机进度仅保存在当前浏览器
题目描述
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究如何将 n 个皇后放置在 n x n 的棋盘上，并且使皇后彼此之间不能互相攻击。给你整数 n，返回所有不同的解，每种解以字符串棋盘形式呈现。
示例：n = 4 有两个解。
解题思路
- 按行放置是关键简化：每行恰好一个皇后，冲突检查只剩列、主对角线（row - col）、副对角线（row + col）三个维度。
- 用三个集合记录已被占用的列与两条对角线，O(1) 判冲突；主对角线差恒定、副对角线和恒定。
- 第 row 行尝试每一列，放置时登记、递归、撤销；row 达到 n 即得到一个完整解并格式化输出。
参考实现
查看参考实现Python · 建议先自行作答
def solveNQueens(n):
res = []
queens = [] # queens[row] = col
cols, diag1, diag2 = set(), set(), set()
def backtrack(row):
if row == n:
res.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in queens])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
queens.append(col)
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1)
queens.pop()
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return res