N皇后问题

N皇后问题是计算机科学中经典的回溯算法问题，旨在将N个皇后放置在N×N的棋盘上，使得它们互不攻击（即任意两个皇后不在同一行、同一列或同一对角线上）。该问题展示了如何通过系统性的尝试和错误（回溯）来寻找所有可能的解。

问题描述

给定一个N×N的棋盘，找到所有合法的皇后布局方式。皇后可以攻击同一行、同一列或同一对角线的任意棋子，因此解必须满足以下条件：

• 每行恰好有一个皇后。
• 每列恰好有一个皇后。
• 任意两个皇后不在同一对角线上。

回溯法解决思路

回溯法的核心是逐步构建候选解，并在发现当前路径无法满足条件时回退（回溯）。对于N皇后问题，步骤如下： 1. **逐行放置皇后**：从第一行开始，尝试在每一列放置皇后。 2. **检查冲突**：确保当前位置与已放置的皇后无冲突（列、对角线）。 3. **递归搜索**：若当前选择有效，递归处理下一行；否则回溯到上一步。 4. **记录解**：当所有行都成功放置皇后时，记录当前布局。

关键优化

• **剪枝**：在放置皇后时立即跳过无效位置，减少递归次数。
• **位运算优化**（高级）：使用位掩码快速检查列和对角线冲突。

代码实现

以下是Python实现的回溯法解决N皇后问题：

  
def solve_n_queens(n):  
    def backtrack(row, cols, diag1, diag2, board, res):  
        if row == n:  
            res.append([''.join(row) for row in board])  
            return  
        for col in range(n):  
            d1, d2 = row - col, row + col  
            if cols[col] or diag1[d1] or diag2[d2]:  
                continue  
            board[row][col] = 'Q'  
            cols[col] = diag1[d1] = diag2[d2] = True  
            backtrack(row + 1, cols, diag1, diag2, board, res)  
            board[row][col] = '.'  
            cols[col] = diag1[d1] = diag2[d2] = False  

    res = []  
    board = [['.' for _ in range(n)] for _ in range(n)]  
    backtrack(0, [False]*n, [False]*(2*n-1), [False]*(2*n-1), board, res)  
    return res  

# 示例：4皇后问题的解  
for solution in solve_n_queens(4):  
    for row in solution:  
        print(row)  
    print()

输出：

  
.Q..  
...Q  
Q...  
..Q.  

..Q.  
Q...  
...Q  
.Q..  

复杂度分析

• **时间复杂度**：最坏情况下为O(N!)，但实际通过剪枝远低于此。
• **空间复杂度**：O(N^2)（存储棋盘）或O(N)（优化后仅记录列/对角线状态）。

实际应用

N皇后问题不仅是算法教学的经典案例，还应用于：

• **电路设计**：避免信号冲突的布局规划。
• **调度问题**：如机场跑道的航班安排。
• **密码学**：构造特定约束的排列组合。

可视化示例

以下是4皇后问题的一个解的可视化：

graph TD A["(0,1)"] --> B["(1,3)"] B --> C["(2,0)"] C --> D["(3,2)"]

对应棋盘：

  
. Q . .  
. . . Q  
Q . . .  
. . Q .  

数学推导

解的数量随N增长呈指数级上升，已知部分解的数量为： $\{\begin{array}{ll}1& \text{当 }N=1\\ 0& \text{当 }N=2,3\\ 2& \text{当 }N=4\\ 92& \text{当 }N=8\\ \end{array}$

扩展阅读

• 尝试修改代码以仅计数解的数量而非存储所有解。
• 研究位运算优化版本以提升大N时的性能。

通过本教程，读者应能理解回溯法的核心思想，并能够将其迁移到其他约束满足问题中。