数据结构与算法自学笔记（17）- N皇后问题与位运算优化版本

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是class40的内容，基于N皇后问题Python实现，分析了经典回溯算法和位运算优化版本的原理与实现。N皇后问题是回溯算法的经典应用，也是展示位运算巧妙应用的绝佳案例。

040【必备】N皇后问题-重点是位运算的版本

问题描述

N皇后问题是在N×N的棋盘上放置N个皇后，使得任意两个皇后都不能相互攻击的问题。皇后可以攻击同一行、同一列或同一对角线上的任何棋子。

测试链接：https://leetcode.cn/problems/n-queens-ii/

核心挑战

N皇后问题的时间复杂度是O(N!)，这意味着随着N的增长，计算量会急剧增加。因此，优化常数时间和进行有效剪枝变得尤为重要。

---

方法一：数组表示路径（经典回溯）

核心思想

使用数组 path[i] = j 表示第i行的皇后放在第j列。对于每一行，尝试所有可能的列位置，通过冲突检测函数判断是否可以放置皇后。

具体实现流程：

1. 在每一行，ban = col | left | right 计算出所有被攻击的位置。（共同的限制）
2. candidate = limit & (~ban) 找出所有可以放置皇后的候选位置（列）。
3. 循环遍历 candidate 中的每一个 1（代表一个可行的列）。
   place = candidate & (-candidate) 是一个巧妙的技巧，用于分离出最右边的 1。
4. 对于每一个可行的 place，递归到下一行，并更新三个位掩码：
   • 列限制: col | place
   • 左对角线限制: (left | place) >> 1 (下一行，对角线向右移一位)
   • 右对角线限制: (right | place) << 1 (下一行，对角线向左移一位)

算法实现

def totalNQueens1(self, n: int) -> int:
    """
    主函数，初始化路径数组并启动递归
    """
    if n < 1:
        return 0
    # path[i] = j 表示第 i 行的皇后放在了第 j 列
    path = [-1] * n
    return self._f1(0, path, n)

def _f1(self, i: int, path: list, n: int) -> int:
    """
    递归函数，尝试在第 i 行放置皇后
    核心思想 (经典回溯法):
    1. 递归地为每一行选择一个列来放置皇后。 
    2. 当处理第 `i` 行时，遍历所有列 `j`。
    3. 对于每个位置 `(i, j)`，检查是否与之前 `0` 到 `i-1` 行已放置的皇后冲突。
    4. 如果不冲突，则将皇后放置在 `(i, j)`，然后递归到下一行 `i+1`。
    5. 递归返回后，隐式地"撤销"选择（因为下一次循环会覆盖 `path[i]`），继续尝试当前行的下一列。
    6. 当 `i` 到达 `n` 时，说明所有 `n` 个皇后都成功放置，找到一个解，返回 1。
    """
    if i == n:
        # 所有行都成功放置了皇后，找到一个有效的解
        return 1
    
    ans = 0
    # 遍历当前 i 行的所有列 j
    for j in range(n):
        # 检查在 (i, j) 位置放皇后是否与之前的皇后冲突
        if self._check(path, i, j):
            # 如果不冲突，记录位置
            path[i] = j
            # 递归到下一行
            ans += self._f1(i + 1, path, n)
    return ans

def _check(self, path: list, i: int, j: int) -> bool:
    """
    检查在(i,j)位置放置皇后是否会与之前的皇后冲突
    """
    # 遍历 0 到 i-1 行，检查冲突
    for k in range(i):
        # path[k] 是第 k 行皇后的列位置
        # 检查列冲突: j == path[k]
        # 检查对角线冲突: abs(i - k) == abs(j - path[k])
        if j == path[k] or abs(i - k) == abs(j - path[k]):
            return False
    return True

冲突检测详解

1. 列冲突：j == path[k] - 同一列不能有两个皇后
2. 对角线冲突：abs(i - k) == abs(j - path[k]) - 对角线上行差的绝对值等于列差的绝对值

算法分析

• 时间复杂度：O(N! × N)，每个位置需要O(N)时间检查冲突
• 空间复杂度：O(N)
• 优缺点：思路清晰但效率较低

---

方法二：位运算优化（推荐）

核心思想

使用三个整数的位信息来表示所有被占用的位置，从而极大地加速冲突检测：

• col：第k位为1表示第k列被占用
• left：第k位为1表示左上到右下对角线被占用
• right：第k位为1表示右上到左下对角线被占用

对角线映射规律

左上到右下对角线（left）

• 特点：行-列的值相同
• 下一行时：对角线向右移动一位，用右移操作 >> 1

右上到左下对角线（right）

• 特点：行+列的值相同
• 下一行时：对角线向左移动一位，用左移操作 << 1

算法实现

def totalNQueens2(self, n: int) -> int:
    """
    主函数，初始化 limit 并启动位运算递归
    """
    if n < 1 or n > 32:
        return 0
    # n = 5 -> limit = 0b11111
    # limit 用于标记棋盘的有效列范围
    limit = (1 << n) - 1
    return self._f2(limit, 0, 0, 0)

def _f2(self, limit: int, col: int, left: int, right: int) -> int:
    """
    位运算递归函数
    
    参数说明：
    - limit: 标记棋盘大小的掩码
    - col: 列占用情况
    - left: 左上到右下对角线占用情况  
    - right: 右上到左下对角线占用情况
    """
    if col == limit:
        # 所有列都被占用，意味着所有皇后都已成功放置，找到一个解
        return 1
    
    # 总限制，合并所有被占用的列和对角线，limit表示是几皇后问题
    ban = col | left | right
    # ~ban : 1可放皇后，0不能放
    # limit & (~ban) 得到当前行所有可以放置皇后的位置
    candidate = limit & (~ban)   #Python 的整数是无限位的，~ban 会把高位也翻成 1，需要用 limit 把有效的 n 位以外的位裁掉。
    
    ans = 0
    # 当还有候选位置时
    while candidate != 0:
        # 提取出最右侧的1，代表本次尝试要放置皇后的位置
        # 例如 candidate = 0b010100, -candidate = 0b101100
        # place = 0b000100
        place = candidate & (-candidate)
        
        # 从候选位置中移除刚刚选择的位置
        candidate ^= place
        
        # 递归到下一行，并更新限制
        ans += self._f2(limit, col | place, (left | place) >> 1, (right | place) << 1) #最终返回的 ans 是：该 n 皇后问题的解的总数
        # col | place: 更新占用列；| 为按位或，把新放皇后的位置并入列占用。
        # (left | place) >> 1: 更新左对角占用；当前行对角占用并上新位置后，右移一位表示到下一行左对角“向右移”。
        # (right | place) << 1: 更新右对角占用；到下一行右对角“向左移”，用左移一位表示。
                    
    return ans

关键位运算技巧

1. 提取最右边的1

place = candidate & (-candidate)

• 原理：-candidate 是 candidate 的补码，两者相与得到最右边的1
• 例子：candidate = 0b010100, -candidate = 0b101100, place = 0b000100

2. 移除已选择的位

candidate ^= place

• 使用异或操作移除已经选择的位置

3. 计算有效候选位置

candidate = limit & (~ban)

• ~ban：翻转ban得到可放置的位置
• limit：确保只考虑有效的n位棋盘范围

执行过程示例

以4皇后问题为例：

初始状态：
limit = 0b1111 (4位棋盘)
col = 0, left = 0, right = 0

第1行：
ban = 0, candidate = 0b1111
可选位置：第0,1,2,3列

选择第0列 (place = 0b0001)：
下一行状态：col=0b0001, left=0b0010, right=0b0010

第2行：
ban = 0b0001 | 0b0010 | 0b0010 = 0b0011
candidate = 0b1111 & 0b1100 = 0b1100
可选位置：第2,3列

... 继续递归

算法分析

• 时间复杂度：O(N!)，但常数时间大幅优化
• 空间复杂度：O(N)
• 优势：位运算操作极快，适合大规模问题

---

性能对比

根据代码测试结果：（测试电脑：联想ThinkBook 16+）

N值	数组方法	位运算方法	性能提升
14	188224	9011	约10倍
14	超时	~10秒内	数十倍

测试代码

if __name__ == '__main__':
    s = Solution()
    n = 14
    
    # 测试方法1
    start_time = time.time()
    ans1 = s.totalNQueens1(n)
    end_time = time.time()
    print(f"方法1答案 : {ans1}")
    print(f"方法1运行时间 : {int((end_time - start_time) * 1000)} 毫秒")

    # 测试方法2
    start_time = time.time()
    ans2 = s.totalNQueens2(n)
    end_time = time.time()
    print(f"方法2答案 : {ans2}")
    print(f"方法2运行时间 : {int((end_time - start_time) * 1000)} 毫秒")

---

位运算核心技巧总结

1. 基本位操作

# 设置第i位为1
num |= (1 << i)

# 清除第i位
num &= ~(1 << i)

# 检查第i位是否为1
if num & (1 << i):

# 翻转第i位
num ^= (1 << i)

2. 高级位技巧

# 提取最右边的1
rightmost_one = num & (-num)

# 清除最右边的1
num &= (num - 1)

# 创建n位全1的掩码
mask = (1 << n) - 1

3. 对角线映射

# 左上到右下：下一行右移
left_diag = (left_diag | place) >> 1

# 右上到左下：下一行左移  
right_diag = (right_diag | place) << 1

---

优化策略总结

1. 数据结构选择

• 数组方法：直观但需要O(N)时间检查冲突
• 位运算方法：用位信息表示状态，O(1)时间冲突检测

2. 状态表示优化

• 用整数的二进制位表示多个布尔状态
• 利用位运算的并行性处理多个位

3. 算法剪枝

• 早期冲突检测
• 状态压缩减少内存访问

4. 常数优化

• 位运算替代数组操作
• 减少函数调用开销

---

学习要点

1. 回溯算法模板

def backtrack(state):
    if is_solution(state):
        record_solution(state)
        return
    
    for choice in get_choices(state):
        if is_valid(choice, state):
            make_choice(choice, state)
            backtrack(state)
            undo_choice(choice, state)  # 回溯

2. 位运算在算法中的应用

• 状态压缩
• 集合操作
• 快速计算
• 空间优化

3. 性能优化思路

• 算法层面：减少时间复杂度
• 实现层面：优化常数因子
• 数据结构层面：选择合适的表示方式

4. 问题分析方法

• 理解问题约束
• 识别状态表示
• 设计状态转移
• 考虑优化空间

---

实际应用场景

1. 约束满足问题（CSP）

• 数独求解
• 图着色问题
• 任务调度

2. 位运算优化适用场景

• 状态空间较小（通常≤64位）
• 需要频繁的集合操作
• 对性能要求极高的场景

3. 工程实践建议

• 先实现清晰版本，再考虑优化
• 位运算虽快但可读性差，需要充分注释
• 在性能关键路径上应用位运算优化

总结

N皇后问题展示了从经典回溯算法到位运算优化的完整演进过程。位运算版本虽然理解难度较高，但在性能上有显著提升，特别适合处理大规模问题。掌握这种优化思路对于解决其他状态空间搜索问题具有重要意义。

通过对比两种方法，我们可以看到算法优化的不同层次：算法设计层面的改进和实现技巧层面的优化。在实际工程中，应该根据具体需求在代码可读性和执行效率之间做出合理权衡。