题目重点：逐行选列，常量平均冲突检查，成对撤销状态；说明对称解、空棋盘与枚举输出成本。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练返回全部n×n棋盘，每行一个Q，其余点；任意两皇后不能同行、同列或同对角线。
- n为非负整数，n=0返回包含一个空布局的列表[[]]，n=2或3无解。
- 旋转和镜像布局分别计为不同结果，不进行对称去重；输出顺序按逐行升序试列确定。
解题路线
- 按行递归，当前row只选一个col，因此同行冲突已由搜索结构排除。无需每次扫描整棋盘，只记录占用列、row−col对角线和row+col反对角线。
- 同一条下降对角线的row−col恒定，同一条上升对角线的row+col恒定；候选若命中任何已占用集合便冲突。两类标识分别保存，不能混到同一集合，因为相同整数不代表同一方向。
- 选合法列后，将列与两对角标识加入集合，chosen追加col，再搜索下一行。返回后全部撤销，包括chosen末项；漏掉任意一个撤销都会污染兄弟分支并漏解。
- 搜索不变量是chosen对应前row行的合法放置，三个集合恰好表示这些皇后。新增合法候选保持不变量，row=n时所有行填满，输出一定合法。每个合法完整布局有唯一的行列序列，逐行枚举不会漏掉，也不会重复。
- 输出时按chosen新建每行字符串，保存独立棋盘；不能把可变chosen本身追加到答案后继续修改。n=0到达基例立即产生一个空布局，这与无解返回空列表是不同含义。
- 不加对角剪枝时，列唯一的完整布局最多n!种，提前冲突能显著减少搜索，但不应声称多项式。此集合版本每个搜索节点仍扫描n列；可给保守O(n·n! + S·n²)界，S为输出布局数。位掩码可以只枚举可用列，需另解释位操作范围。
- 对称优化可只搜首行一半再镜像，但奇数n的中间列要单独处理；如果题目只数解，保存所有棋盘是浪费。若要求本质不同解，须比较完整D4等价类，而非简单除以8。
手动走一遍
n=4有两个列序列[1,3,0,2]和[2,0,3,1]，互为镜像但本合同两者都输出。n=1输出Q，n=2与3空列表；回溯撤销后第二个首列分支不能残留第一个分支的对角占用。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def n_queens(n):
if type(n) is not int or n < 0:
raise ValueError('expected nonnegative integer n')
answers, chosen = [], []
columns, down, up = set(), set(), set()
def search(row):
if row == n:
answers.append(['.' * col + 'Q' + '.' * (n - col - 1) for col in chosen])
return
for col in range(n):
if col in columns or row - col in down or row + col in up:
continue
columns.add(col)
down.add(row - col)
up.add(row + col)
chosen.append(col)
search(row + 1)
chosen.pop()
columns.remove(col)
down.remove(row - col)
up.remove(row + col)
search(0)
return answers
复杂度
保守时间O(n·n! + S·n²)，棋盘输出S份各n²字符；不含输出的递归、chosen和集合O(n)工作空间，输出O(S·n²)。递归深度n，大n需考虑语言栈限制。
易错点与追问
容易失分的边界
- row−col与row+col放在同一集合。
- 递归后漏撤销某个占用标记。
- 保存可变路径引用造成所有答案相同。
- 未定义对称政策便把解数除以8。
继续深挖
- 只数解怎样减少输出存储？
- 位掩码available与低位提取怎样写？
- 固定某些皇后或禁止格怎样适配？
- 如何去除旋转与镜像等价布局？
