【算法】【Python】N皇后问题的三种解法

N皇后问题是指在 N×N 的国际象棋棋盘上摆放 N 个皇后，使得它们彼此之间不能互相攻击（不能同一行、同一列、同一斜线）。

算法	速度	占用空间	易实现	适用规模
回溯法	慢（指数级）	少	简单	一般 ≤ 12
分支限界法	快（剪枝）	中	略复杂	一般 ≤ 15
位运算优化回溯法	极快（更少判断）	极少	中等	可支持到20+

# 回溯法
def solve_n_queens_backtracking(n):
    solutions = []
    board = [-1] * n

    def is_safe(row, col):
        for i in range(row):
            if board[i] == col or \
               abs(board[i] - col) == abs(i - row):
                return False
        return True

    def backtrack(row=0):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                backtrack(row + 1)
                board[row] = -1

    backtrack()
    return solutions

# 分支限界法
def solve_n_queens_branch_and_bound(n):
    solutions = []
    board = [-1] * n
    cols = [False] * n
    diag1 = [False] * (2 * n - 1)
    diag2 = [False] * (2 * n - 1)

    def solve(row=0):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if not cols[col] and not diag1[row + col] and not diag2[row - col + n - 1]:
                board[row] = col
                cols[col] = diag1[row + col] = diag2[row - col + n - 1] = True
                solve(row + 1)
                cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False

    solve()
    return solutions

# 优化-位运算法
def solve_n_queens_bitwise(n):
    solutions = []

    def dfs(row, cols, hills, dales, state):
        if row == n:
            solutions.append(state[:])
            return
        free_positions = (~(cols | hills | dales)) & ((1 << n) - 1)
        while free_positions:
            curr = free_positions & -free_positions
            col = bin(curr - 1).count("1")
            state.append(col)
            dfs(row + 1,
                cols | curr,
                (hills | curr) << 1,
                (dales | curr) >> 1,
                state)
            state.pop()
            free_positions &= free_positions - 1

    dfs(0, 0, 0, 0, [])
    return solutions

import time

# 性能测试
def benchmark(n):
    print(f"测试 n = {n}")

    start = time.time()
    b1 = solve_n_queens_backtracking(n)
    print(f"回溯法: {len(b1)} 个解, 用时: {time.time() - start:.4f} s")

    start = time.time()
    b2 = solve_n_queens_branch_and_bound(n)
    print(f"分支限界法: {len(b2)} 个解, 用时: {time.time() - start:.4f} s")

    start = time.time()
    b3 = solve_n_queens_bitwise(n)
    print(f"优化-位运算法: {len(b3)} 个解, 用时: {time.time() - start:.4f} s")

n = 10
benchmark(n)

测试 n = 10
回溯法: 724 个解, 用时: 0.4371 s
分支限界法: 724 个解, 用时: 0.0610 s
优化-位运算法: 724 个解, 用时: 0.0688 s

当n = 12时

测试 n = 12
回溯法: 14200 个解, 用时: 11.4715 s
分支限界法: 14200 个解, 用时: 1.3766 s
优化-位运算法: 14200 个解, 用时: 1.3221 s

回溯法（Backtracking）——暴力剪枝

核心思路

从第 0 行开始尝试放皇后，每一行依次向下尝试，保证：

• 当前皇后不在同一列（列冲突）
• 当前皇后不在对角线（斜线冲突）

算法流程

1. 枚举第 row 行所有列 col。
2. 检查 (row, col) 是否安全（不被已有皇后攻击）。
3. 如果安全，就将皇后放在 (row, col)，进入下一行递归。
4. 回溯：撤销当前皇后的摆放，尝试下一个位置。

优点

• 容易理解，适合入门搜索与回溯。

缺点：

• 没有记录重复计算的位置，效率低。
• 判断是否安全用循环查找，时间较长。

分支限界法（Branch & Bound）——剪枝增强版

核心思路

回溯的基础上，用三个布尔数组提前记录哪些列和对角线已经被占用，大幅减少检查耗时。

状态表示

• cols[col]：表示第 col 列是否已有皇后。
• diag1[row + col]：主对角线（↘）是否被占用。
• diag2[row - col + n - 1]：副对角线（↙）是否被占用。

算法流程

1. 每次尝试放置时，只查数组是否允许，O(1) 判断。
2. 放皇后时同时更新 cols, diag1, diag2。
3. 回溯时撤销标记。

优点

• 判断效率从 O(n) 降为 O(1)，速度显著提升。
• 空间换时间。

缺点

• 多了状态维护，稍微复杂。

位运算优化（Bitwise Backtracking）——极限压缩

核心思路

再进一步优化，将 cols, diag1, diag2 用整数的二进制位来表示：

• cols = 0b0101：表示第 0 和 2 列被占用
• ~(cols | hills | dales)：快速得到当前合法列的位置

算法流程

1. 每一位代表一个列是否被占用，32位以内直接用一个整数表示所有列。
2. 使用 lowbit 技巧快速提取当前可以尝试的列。
   • curr = free_positions & -free_positions
3. 移位操作更新斜线占用状态（向左、右一位）。

优点

• 内存压缩、速度极快，能支持到 n=20+。
• 所有判断、更新状态全是位运算（极快）。

缺点

• 难度高。

方法	本质思路	剪枝策略
回溯法	DFS暴力尝试 + 安全检查	判断冲突 O(n)
分支限界法	DFS + O(1)判断 + 状态标记	用数组记录是否占用
位运算优化回溯	DFS + 位掩码剪枝 + 移位压缩	全程位运算，极快