回溯算法解决N皇后问题 问题描述 N皇后问题要求在一个N×N的棋盘上放置N个皇后，使得它们互不攻击（即任意两个皇后不能处于同一行、同一列或同一对角线上）。需要找出所有可能的放置方案。 解题思路分析 关键约束 ： 每行只能放一个皇后（天然满足，因按行逐行放置）。 每列只能有一个皇后。 每条对角线（主对角线和反对角线）只能有一个皇后。 回溯核心思想 ： 从第一行开始，尝试在每一列放置皇后，若当前放置满足约束，则递归进入下一行。 若某一行所有列都无法放置，则回溯到上一行调整皇后位置。 当成功放置到第N行时，记录一个有效解。 步骤详解 1. 定义约束检查的数据结构 使用三个集合或数组来记录已占用的列、主对角线和反对角线： cols ：标记已被占用的列。 diag1 ：主对角线（左上到右下），其索引可计算为 row - col + (N-1) （或直接 row - col ，但需处理负数）。 diag2 ：反对角线（右上到左下），其索引为 row + col 。 2. 回溯函数设计 参数：当前行 row 、临时棋盘状态 board 、结果列表 res 。 终止条件： row == N ，表示所有行已放置完毕，将当前棋盘加入结果。 遍历当前行的每一列 col ： 若 col 或对应对角线已被占用，跳过。 否则放置皇后，标记列和对角线，递归进入下一行。 递归返回后撤销标记（回溯）。 3. 对角线索引计算示例（以4×4棋盘为例） 主对角线索引： row - col 可能为负，需偏移为 row - col + (N-1) ，确保范围在 [0, 2N-2] 。 反对角线索引： row + col 范围在 [0, 2N-2] 。 实例演示（N=4） 第一行放置皇后在列0： 标记列0、主对角线0（0-0+3=3）、反对角线0（0+0=0）。 第二行尝试列0（冲突）→列1（冲突，主对角线0-1+3=2被占用？未占用，但列1未被占，反对角线1+1=2未占，实际可放置？需验证）： 正确计算：主对角线索引=1-1+3=3（与第一行冲突），故列1不可用。继续尝试直到找到合法位置。 通过回溯最终找到解，如 [1, 3, 0, 2] 表示每行皇后所在列。 优化与复杂度 时间复杂度：O(N !)，因每行选择减少，但通过约束剪枝避免全排列。 空间复杂度：O(N)用于递归栈和标记数组。 总结 N皇后问题通过回溯算法系统性地尝试所有可能放置，并利用约束条件剪枝无效分支，体现了回溯“试错+回退”的核心思想。掌握对角线索引计算和状态撤销是实现的关键。