题目定位
这是经典的约束型回溯题，真正关键的是剪枝，而不是单纯递归，因为非法棋盘状态必须尽早淘汰。
关键观察
每一行真正需要维护的信息只有哪些列、主对角线和副对角线已被占用。
目标复杂度
Exponential / O(n)
这题的解法思路怎么拆
1
这是经典的约束型回溯题，真正关键的是剪枝，而不是单纯递归，因为非法棋盘状态必须尽早淘汰。
2
每一行真正需要维护的信息只有哪些列、主对角线和副对角线已被占用。
3
先把决策树结构建出来。
4
确定当前层候选集怎么生成。
参考实现
Python# Generic pattern template
def backtrack(path):
if complete(path):
answer.append(path[:])
return
for choice in choices(path):
if not valid(choice, path):
continue
path.append(choice)
backtrack(path)
path.pop()
常见坑点
warning
每次尝试都整张棋盘检查，而不是维护列和对角线集合。
warning
对角线索引规则写错。
高频追问
对角线集合和行列是怎样映射的？
能不能进一步用 bitmask 优化？
继续刷相关题
先把 回溯 这个模式刷成体系，再去做更难变体。