第70课 - N皇后问题

学习目标

理解N皇后问题的定义与约束条件
掌握使用回溯算法解决N皇后问题的标准框架
学会利用集合或数组进行冲突检测（剪枝）
能够将算法的解空间树形象化，并理解其搜索过程

核心概念

什么是N皇后问题？ N皇后问题是一个经典的组合优化问题：要求在 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后都不能互相攻击。皇后的攻击范围是其所在的同一行、同一列、以及两条对角线。

核心思路：回溯 由于皇后不能同行，我们可以一行一行地来放置皇后，这样就天然避免了行冲突。对于每一行，我们尝试将皇后放在该行的每一列，并通过检查来确保这个位置与之前已经放置的皇后不发生列冲突和对角线冲突。

如果检查通过，我们就继续递归地处理下一行。如果下一行的所有位置都无法放置皇后（即导致冲突），我们就回溯到上一行，撤销上一行皇后的位置，并尝试该行的下一个列。

冲突检测（剪枝） 回溯的效率高度依赖于“剪枝”的能力——尽早排除不可能产生解的分支。在N皇后问题中，我们需要快速判断一个(row, col)位置是否合法。

列冲突：我们需要记录哪些列已经被占用了。可以用一个布尔数组cols，长度为N，cols[c]=True表示第c列已被占用。
对角线冲突：关键技巧。棋盘有两条方向的对角线：
- 主对角线（左上-右下 \ ）：对于主对角线上的格子，其 行号 - 列号 的值是恒定的。例如，(0,0), (1,1), (2,2) 的row - col都是0。我们可以用一个集合diag1来存储被占用的row - col值。
- 副对角线（左下-右上 / ）：对于副对角线上的格子，其 行号 + 列号 的值是恒定的。例如，(0,2), (1,1), (2,0) 的row + col都是2。我们可以用一个集合diag2来存储被占用的row + col值。

在放置(row, col)位置的皇后前，只需检查cols[col]、(row-col) in diag1或(row+col) in diag2是否为True。只要有一个为True，则该位置非法。

代码示例

下面是一个使用Python实现的N皇后问题解法，能够找到并打印所有的解。

def solve_n_queens(n):
    """
    解决N皇后问题，并返回所有可能的解。
    :param n: 皇后数量，也是棋盘大小。
    :return: 一个列表，每个元素是一个解，解用一个长度为n的列表表示，其中第i个元素是第i行皇后所在的列号。
    """
    # 用于存储所有解的列表
    solutions = []
    # 三个集合，用于记录列、主对角线、副对角线的占用情况
    cols = set()      # 存储被占用的列号
    diag1 = set()     # 存储被占用的主对角线索引 (row - col)
    diag2 = set()     # 存储被占用的副对角线索引 (row + col)
    # 用于存储当前路径（当前部分解）的列表，path[i] 表示第i行皇后所在的列
    current_path = []

    def backtrack(row):
        # 递归终止条件：如果已经成功放置了所有行（0到n-1）的皇后，则找到一个解
        if row == n:
            solutions.append(current_path[:]) # 将当前路径（解）的副本加入结果
            return

        # 尝试将当前行(row)的皇后放在每一列(col)上
        for col in range(n):
            # 检查当前位置(row, col)是否与已放置的皇后冲突
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue # 冲突，跳过该列，尝试下一列

            # 做出选择：将皇后放在(row, col)
            current_path.append(col)
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

            # 递归进入下一行
            backtrack(row + 1)

            # 撤销选择（回溯），尝试当前行的下一列
            current_path.pop()
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    # 从第0行开始回溯
    backtrack(0)
    return solutions

def print_board(solution):
    """将解格式化并打印成棋盘样式"""
    n = len(solution)
    board = []
    for col in solution:
        # 每一行，皇后所在列用'Q'表示，其他用'.'
        row_str = '.' * col + 'Q' + '.' * (n - col - 1)
        board.append(row_str)
    return board

# 测试代码
if __name__ == "__main__":
    n = 4
    all_solutions = solve_n_queens(n)
    print(f" {n}皇后问题共有 {len(all_solutions)} 个解。")
    for i, sol in enumerate(all_solutions):
        print(f"\n解 {i+1}:")
        board = print_board(sol)
        for row in board:
            print(row)

运行结果（n=4）：

 4皇后问题共有 2 个解。

解 1:
..Q.
Q...
...Q
.Q..

解 2:
.Q..
...Q
Q...
..Q.

实践练习

1. 修改与观察

修改上述代码中的n值，分别运行n=1, 2, 3, 4, 5，观察解的数量变化。
（思考题）对于n=2和n=3，解的数量是多少？为什么？

2. 只输出第一个解

修改solve_n_queens函数，使其在找到第一个解后就立即停止搜索并返回，而不是寻找所有解。
提示：在递归函数中，当找到一个解时，可以通过一个全局标志位或通过函数返回值来控制递归的终止。

3. 位运算优化（挑战）

使用位运算（Bit Manipulation）来代替集合进行冲突检测，这能进一步提升算法效率。
思路：用一个整数的二进制位来表示列的占用情况。同样，主对角线和副对角线的冲突也可以用位运算快速计算。请尝试实现这一优化版本。

常见错误

忘记回溯时撤销状态：在递归调用后，必须将当前行的选择（加入cols、diag1、diag2的操作）撤销，否则会影响后续分支的搜索。这是回溯算法中最核心也最容易出错的一步。
对角线计算错误：主对角线索引计算为row - col，可能为负数。Python的集合可以处理负数，没有问题。但在其他语言中，如果使用数组，通常需要加上一个偏移量（如n-1）来使其变为非负数。
边界条件处理：对于n=0或n=1的情况，代码需要能正确处理。n=0时应返回一个包含空解的列表（或特定结果），n=1时应返回一个解[[0]]。
解路径的记录方式：初学者可能会尝试用一个二维数组来实时记录棋盘状态，但这会增加空间和时间复杂度。用一行一个列号的列表来记录路径，是一种更简洁高效的方案。

小结

问题本质：N皇后问题是在满足严格约束条件下的组合搜索问题。
回溯框架：采用一行一行放置的策略，将问题分解为一系列的决策步骤。对于每一步（每行），尝试所有可能的选项（列），检查约束，并递归。
冲突检测（剪枝）：利用三个集合（或数组/位掩码）分别记录列、主对角线、副对角线的占用情况，是快速判断一个位置是否安全的关键。理解(row-col)和(row+col)能够唯一标识一条对角线是解题的技巧核心。
回溯的精髓：当当前选择无法导向可行解时，撤销选择并尝试其他分支。current_path, cols, diag1, diag2 这四个数据结构的同步添加与删除，是回溯正确性的保障。
复杂度：该回溯解法的时间复杂度在最坏情况下仍是指数级的，但有效的剪枝可以大幅减少实际搜索空间。

掌握N皇后问题，不仅学会了回溯算法的一个经典应用，更重要的是理解了如何将复杂的约束条件转化为高效的数据结构（集合）进行检查，这是解决许多搜索问题的通用思路。下一课，我们将用类似的回溯思想来解决另一个经典问题——数独。

练习编辑器

rust

N 皇后问题