题解

核心算法

逐行放置，用三个布尔数组标记列、主对角线和副对角线。

思路推导

每行恰放一个皇后，冲突标记排除所有非法位置；叶子即为完整方案。

正确性说明

按照上述状态含义与转移顺序，每一步只使用已经正确求出的子问题；所有合法情况被完整计入，且互斥分类不会重复计数，因此最终输出即为题目所求。

复杂度

• 时间复杂度：O(n!)
• 空间复杂度：O(n)

易错点

两个对角线下标分别为 r-c+n 与 r+c。

完整标程见 std/main.cpp。