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!)，實際效率相近，選擇依據具體場景需求。