📢 本文由 gemini-3-flash-preview 翻譯
問題描述
n-皇后問題是在 n 列 n 行的棋盤上放置 n 個皇后，使得皇后彼此之間不受攻擊，其規則是任意兩個皇后不在同一列、同一行和相同的對角線上 (也就是國際象棋的皇后移動範圍)。
問題分析
擬採用以下思路解決 n-皇后問題：
第 i 個皇后放在第 i 列
從第一個皇后開始，對於每個皇后，從其對應列 (第 i 個皇后對應第 i 列) 的第一行開始嘗試
若可以放置，確定位置，考慮下一個皇后
若與之前的皇后衝突，則考慮下一行
若超出最後一行，則重新確定上一個皇後的位置
重複該過程，直到找到所有的放置方案
C 程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <stdio.h>
#include <math.h>
#define N 4 // 皇后個數
// 判斷第 k 個皇后目前放置位置是否與前面的皇后衝突
int isplace(int pos[], int k){
int i;
for(i=1; i<k; i++){
if(pos[i]==pos[k] || fabs(i-k) == fabs(pos[i]-pos[k]))
return 0;
}
return 1;
}
int main(){
int i,j;
int count = 1;
int pos[N+1];
// 初始化位置
for(i=1;i<=N;i++)
pos[i]=0;
j = 1;
while(j>=1){
pos[j]=pos[j]+1;
// 嘗試擺放第 i 個皇后
while(pos[j]<=N && !isplace(pos,j)){
pos[j]=pos[j]+1;
// 得到一個擺放方案
}
if(pos[j]<=N && j==N){
printf("方案 %d：", count++);
for(i=1;i<=N;i++)
printf("%d", pos[i]);
printf("\n");
}
// 考慮下一個皇后
if(pos[j]<=N && j<N){
j+=1;
}else{ // 返回考慮上一個皇后
pos[j]=0;
j-=1;
}
}
return 1;
}
|