N皇后問題是一個經典的算法問題，要求在N×N的棋盤上放置N個皇后，使得它們互不攻擊。本文將全面解析該問題的解法，特別聚焦于DFS算法和對角線優化的數學原理。
問題描述
在N×N的國際象棋棋盤上放置N個皇后，要求：
-
任意兩個皇后不在同一行
-
任意兩個皇后不在同一列
-
任意兩個皇后不在同一對角線
數據結構圖解
1. 棋盤表示
char g[N][N]; // 棋盤矩陣
'.'?表示空位
'Q'?表示皇后
示例（n=4初始狀態）：
. . . . . . . . . . . . . . . .
2. 沖突檢測數組
bool col[N]; // 列占用標記 bool dg[N*2]; // 正對角線占用標記 bool udg[N*2]; // 反對角線占用標記
對角線索引計算：
(0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3)
正對角線(dg)：
u + i（行+列）
例如：(1,2)的正對角線索引=1+2=3
我們發現同一個對角線的上的坐標的x,y值相加是相等的，所以我們用dg[u+i]去標記
反對角線(udg)：
n - u + i
例如：當n=4時，(1,2)的反對角線索引=4-1+2=5
反對角線，我們此時不能再次使用u+i了?
但為了確保索引不重疊，我們使用
n - u + i：
當
u增加時，n - u減小當
i增加時，i增大這樣確保每條反對角線有唯一索引
實際計算示例（n=4）
坐標 計算式 索引值 (0,3) 4-0+3=7 7 (1,2) 4-1+2=5 5 (2,1) 4-2+1=3 3 (3,0) 4-3+0=1 1
算法執行流程圖解
DFS遞歸過程
dfs(0) ├─ 嘗試第0行第0列 │ ├─ 放置皇后 │ ├─ dfs(1) │ │ ├─ 嘗試第1行第2列 │ │ │ ├─ 放置皇后 │ │ │ ├─ dfs(2) │ │ │ │ ├─ (沖突，回溯) │ │ │ └─ 撤銷皇后 │ │ └─ 嘗試其他列... │ └─ 撤銷皇后 └─ 嘗試第0行第1列├─ 放置皇后├─ dfs(1)│ ├─ 嘗試第1行第3列│ │ ├─ 放置皇后│ │ ├─ dfs(2)│ │ │ ├─ 找到解│ │ │ └─ 輸出棋盤│ │ └─ 撤銷皇后│ └─ 嘗試其他列...└─ 撤銷皇后
示例解（n=4）
有效解之一：
. Q . . . . . Q Q . . . . . Q .
對應的標記數組狀態：
-
col: [1, 0, 1, 0] (第0、2列被占用)
-
dg: 索引1、3、4被占用
-
udg: 索引4、5、6被占用
完整代碼
/*DFS 深度優先搜索*/ #include <stdio.h> #include <stdbool.h>#define N 20int n; //棋盤的大小(n*n) char g[N][N]; //模擬棋盤,'.'表示空，'Q'表示皇后 //col表示列是否被占用，dg表示正對角線是否被占用，udg表示反對角線是否被占用 bool col[N], dg[N*2], udg[N*2]; void dfs(int u) //u表示當前處理的行 {if (u == n) //所有的行處理完畢,輸出解,返回遞歸{for (int i = 0;i < n;i++) //puts函數輸出字符串,自動換行puts(g[i]); //在二維數組g[][]中,單使用g[i]表示第i行的所有數據puts(""); //打印空格,隔開不同解return;}//嘗試在當前行的每一列放置皇后for(int i = 0;i < n;i++)//檢查列,正對角線,反對角線是否沖突if (!col[i] && !dg[u + i] && !udg[n - u + i]){g[u][i] = 'Q'; //防止皇后col[i] = dg[u + i] = udg[n - u + i] = true; //標記占用dfs(u + 1); //遞歸處理下一行col[i] = dg[u + i] = udg[n - u + i] = false; //回溯,撤銷原有的標記g[u][i] = '.'; //恢復棋盤} }int main() {scanf("%d", &n);//初始棋盤for (int i = 0;i < n;i++)for (int j = 0;j < n;j++)g[i][j] = '.';//從第0行開始DFSdfs(0);return 0; }
時間復雜度分析
-
最壞情況：O(n!)（需要嘗試所有可能的排列）
-
實際由于剪枝（沖突檢測），運行效率高于純暴力搜索
關鍵點總結
-
行處理順序：逐行放置皇后，避免行沖突
-
沖突檢測：
-
列沖突：
col[i] -
正對角線沖突：
dg[u+i] -
反對角線沖突：
udg[n-u+i]
-
-
回溯機制：遞歸返回時撤銷所有修改
這個算法通過DFS系統地探索所有可能的解空間，同時使用剪枝技術大幅提高效率。
