Java实现N皇后问题的双路径探索：递归回溯与迭代回溯算法详解

N皇后问题要求在N×N的棋盘上放置N个皇后，使得她们无法互相攻击。本文提供递归和循环迭代两种解法，并通过图示解释核心逻辑。

---

一、算法核心思想

使用回溯法逐行放置皇后，通过冲突检测保证每行、每列、对角线上只有一个皇后。发现无效路径时回退到上一状态。

冲突检测条件（关键）：

1. 同列冲突：col[i] == col[j]
2. 对角线冲突：abs(col[i] - col[j]) == abs(i - j)

---

二、递归版本实现

1. 流程图

2. 时序图

3. 代码解释

：

1. 程序目的
   该代码用于解决N皇后问题，即在N×N棋盘上放置N个皇后，使其互不攻击（即任意两个皇后不在同一行、列或对角线上），返回所有可能的解。
2. solveNQueens方法
   • 初始化结果列表result，用于存储所有解。
   • 调用backtrack方法启动递归回溯过程。
   • 参数n表示棋盘大小，cols数组记录每行皇后所在的列位置（索引为行，值为列）。
3. backtrack递归核心
   • 终止条件：当row == n时，表示所有皇后已正确放置，将当前cols数组的拷贝加入结果（避免后续修改影响结果）。
   • 递归逻辑：遍历当前行的每一列col，若位置有效则放置皇后（cols[row] = col），并递归处理下一行（row + 1）。
4. isValid冲突检查
   • 检查当前列col与之前所有行（0到row-1）的皇后是否冲突：
     • 列冲突：cols[i] == col，即同一列已有皇后。
     • 对角线冲突：Math.abs(col - cols[i]) == row - i，即行差等于列差绝对值。
   • 若任一条件满足，返回false，否则位置有效。
5. 主函数测试与输出
   • 测试n=4的皇后问题，调用solveNQueens获取所有解。
   • 使用Lambda表达式遍历打印每个解（如[1, 3, 0, 2]表示第0行皇后在1列，第1行在3列等）。
6. 关键实现细节
   • 回溯剪枝：仅尝试有效位置，减少递归次数。
   • 结果存储：每次成功时创建新的ArrayList保存当前解，避免引用问题。
   • 递归层次：每层递归处理一行皇后，确保每行只有一个皇后。

示例输出：
对于n=4，输出两个解：[1, 3, 0, 2]和[2, 0, 3, 1]，对应两种不同的棋盘布局方式。

4. 代码实现
   1. 注意：下标从0开始

import java.util.ArrayList;
import java.util.List;public class NQueensRecursive {public static List<List<Integer>> solveNQueens(int n) {List<List<Integer>> result = new ArrayList<>();backtrack(n, 0, new Integer[n], result);return result;}private static void backtrack(int n, int row, Integer[] cols, List<List<Integer>> result) {if (row == n) {result.add(new ArrayList<>(List.of(cols)));return;}for (int col = 0; col < n; col++) {if (isValid(cols, row, col)) {cols[row] = col;backtrack(n, row + 1, cols, result);}}}private static boolean isValid(Integer[] cols, int row, int col) {for (int i = 0; i < row; i++) {if (cols[i] == col || Math.abs(col - cols[i]) == row - i) {return false;}}return true;}public static void main(String[] args) {List<List<Integer>> solutions = solveNQueens(4);solutions.forEach(System.out::println);}
}

---

三、循环迭代版本实现

1. 时序图

2. 流程说明

1. 初始化阶段：
   • 清空皇后位置数组
   • 从第一个皇后开始放置（j=1）
2. 主循环逻辑：
   • 每次循环尝试将当前皇后的位置右移一格
   • 通过check()验证当前位置是否：
     • 与已有皇后同列
     • 处于同一斜线
   • 合法时继续处理下一个皇后，非法时继续右移
   • 当完成最后一列放置时输出有效方案
3. 回溯机制：
   • 当某列所有位置尝试失败后
   • 重置当前列位置为0
   • 回溯到前一列继续尝试新位置
4. 终止条件：
   • 当回溯到j=0时说明所有可能性已穷尽
   • 程序正常结束

该实现通过非递归方式实现了经典的回溯算法，使用while循环和位置重置机制替代了递归调用栈，具有较好的空间效率。

3. 代码实现
   1. 注意：下标从1开始

public class Test {// 定义4个皇后static final  Integer N = 4;// 存储皇后的列号static int[] q =  new int[N+1];// 方案数static int answer =0;public static void main(String[] args) {queen();}public static boolean check(int j){for(int i=1;i<j;i++){if(q[i]==q[j] || Math.abs(i-j)==Math.abs(q[i]-q[j])){ // 判断是否同列或同一斜线return false;}}return true;}public static void queen(){queenInit();int j = 1; // 表示正在摆放第j个皇后while(j>=1){q[j] ++;// 让第j个皇后的位置加1while(!check(j) && q[j]<=N){ // 不满足条件的话，就一直向后移动,为了防止越界，还需要判断q[j]的长度q[j]++;}// 判断if(q[j]<=N){// 表示第j个位置，合法if(j==N){// 最后一个皇后已经摆放完毕了answer++;System.out.print("方案"+answer);System.out.print("结果为：");for (int i = 1; i <=N ; i++) {System.out.print(q[i]+",");}System.out.println();}else{// 继续找下一个皇后的摆放位置j++;}}else{// 没有位置摆放了，需要回溯到上一次。q[j]=0; // 重置位置j--;}}}// 皇后初始化public static void queenInit(){for(int i=1;i<=N;i++){q[i]=0;}}
}

---

四、算法流程图示（以4皇后为例）

步骤分解：

1. 放置行0的皇后在列0Q . . .. . . .. . . .. . . .2. 行1尝试列0（冲突）→ 尝试列1（冲突）→ 列2有效Q . . .. . Q .. . . .. . . .3. 行2尝试所有列均冲突，回溯到行1Q . . .. . . . ← 行1无法继续. . . .. . . .4. 行1移动到列3Q . . .. . . Q. . . .. . . .5. 行2尝试列1有效Q . . .. . . Q. Q . .. . . .6. 行3无有效列，回溯→最终找到解：[1, 3, 0, 2] 对应棋盘：. Q . .. . . QQ . . .. . Q .

---

五、算法对比

特性	递归版本	循环迭代版本
代码复杂度	简洁，易理解	需手动管理状态栈
内存消耗	有栈深度限制	显式栈结构，可控性强
适用场景	小规模数据，代码可读性优先	避免栈溢出，大数据量更稳定

两种方法时间复杂度均为O(N!)，实际效率相近，选择依据具体场景需求。