八皇后问题

"""
八皇后问题
"""
def solve_n_queens(n):
    def backtrack(row, cols, diag1, diag2):
        """
        row: 当前正在放置的行
        cols: 已经放置皇后的列集合
        diag1: 已经放置皇后的主对角线集合 (row - col)
        diag2: 已经放置皇后的副对角线集合 (row + col)
        """
        if row == n:  # 如果成功放置了n行，说明找到一种解法
            return 1
        
        solutions = 0
        for col in range(n):
            d1 = row - col  # 主对角线标识
            d2 = row + col  # 副对角线标识
            
            # 检查当前位置的列和对角线是否已有皇后
            if col in cols or d1 in diag1 or d2 in diag2:
                continue  # 冲突，跳过当前位置
            
            # 做选择：在此处放置皇后
            cols.add(col)
            diag1.add(d1)
            diag2.add(d2)
            
            # 递归进入下一行
            solutions += backtrack(row + 1, cols, diag1, diag2)
            
            # 撤销选择（回溯）
            cols.remove(col)
            diag1.remove(d1)
            diag2.remove(d2)
            
        return solutions

    # 从第0行开始搜索
    return backtrack(0, set(), set(), set())

print(f"八皇后问题的正确解法数量为: {solve_n_queens(8)}")

这段代码实现的是经典的**八皇后问题**（N皇后问题的特例），它使用**回溯算法**来找出所有合法的皇后放置方式，并统计解的数量。

下面我将从实现原理、用途和注意事项三个方面为您详细解释这段代码：

### 一、 实现原理

八皇后问题的核心规则是：在一个 8×8 的棋盘上放置8个皇后，使得任意两个皇后都不在同一行、同一列、也不在同一对角线上。

这段代码通过**深度优先搜索（DFS）**加**回溯**的思想来解决这个问题：

1. 逐行放置：代码采用按行放置的策略，每次递归调用处理一行row），这样天然保证了每一行只有一个皇后，无需检查行冲突。

2. 冲突检测（核心技巧）：

* 列冲突：使用集合 cols 记录已经被占用的列。如果 col in cols，说明该列已有皇后。

* 主对角线冲突（左上到右下）：在同一条主对角线上的所有格子，其 行号 - 列号 (row - col) 的值是相等的。因此，用集合 diag1 记录 row - col 即可代表一整条主对角线。

* 副对角线冲突（右上到左下）：在同一条副对角线上的所有格子，其 行号 + 列号 (row + col) 的值是相等的。同理，用集合 diag2 记录 row + col 即可代表一整条副对角线。

* 这种利用数学特性将对角线坐标映射为一个整数的方法，极大提高了冲突检测的效率。

3. 回溯过程：

* 做选择：如果当前 (row, col) 位置没有冲突，就将皇后放上去（把对应的列和对角线标识加入集合）。

* 递归：进入下一行 backtrack(row + 1, ...) 继续放置。

* 撤销选择：从下一行返回后，把刚才放置的皇后拿走（从集合中移除对应的标识），恢复现场，以便尝试当前行的其他列。

4. 终止条件：当 row == n 时，说明成功在 n 行都放置了皇后，找到了一个有效解，返回 1 并向上累加。

### 二、 用途

1. 算法教学与面试：N皇后问题是学习递归、回溯算法和深度优先搜索（DFS）最经典的案例，经常出现在各大公司的编程面试中。

2. 约束满足问题（CSP）的缩影：现实生活中的很多问题（如排课表、任务调度、数独等）都可以抽象为在特定约束下寻找可行解的问题，八皇后问题的解题思路可以直接迁移。

3. 组合数学研究：用于计算和验证N皇后问题在更大棋盘上的解的数量。

### 三、 注意事项

1. 时间复杂度：

在最坏情况下，回溯算法的时间复杂度是 $O(N!)$。虽然通过剪枝（提前跳过冲突位置）避免了大量无效搜索，但随着 $N$ 的增大，计算量依然呈指数级上升。这段代码在 $N=8$ 时瞬间就能跑完，但如果 $N$ 超过 14 或 15，运行时间会变得非常长。

2. 空间复杂度：

空间复杂度主要取决于递归调用栈的深度和用于记录冲突的集合大小，为 $O(N)$。相比于使用二维数组模拟整个棋盘，这种仅用三个集合记录状态的方法非常节省内存。

3. 输出形式：

这段代码**只输出解的数量**，并不输出具体的棋盘摆放方案。如果您需要看到具体的摆放图案，需要在递归到 row == n 时，将当前的放置路径（比如用一个列表记录每一行皇后所在的列）保存下来，而不是仅仅返回 1。

4. 集合操作的效率：

代码中使用了 Python 的 set，其 in 和 addremove 操作的平均时间复杂度为 $O(1)$。如果改用列表，冲突检测的时间复杂度会退化为 $O(N)$，导致整体运行效率大幅下降。为了追求极致性能，还可以使用**位运算**来代替集合，这在处理大规模N皇后问题时是更优的常规手段。

如果您有任何关于代码修改（例如：如何打印出具体的棋盘图案）或其他问题，随时可以问我！