回溯算法---n皇后问题_#define num 20 int n; int x[num]; int sum; void ba

在n×n格的棋盘上放置彼此不受攻击的n个皇后。
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

由于棋盘的每列/行只有一个皇后，所以可以用一维向量X( x1, x2, …, xn)，其中xi∈{1, 2, …, n}，表示第i列皇后所在的行x[i]，即解空间的每个结点都有n个儿子，因此解空间的大小为nn，这是一棵子集树。

n皇后问题回溯算法的数据结构

#define NUM 20
int n;			//棋盘的大小
int x[NUM];		//解向量
int sum;		//当前已经找到的可行方案数

1
2
3
4
5

n皇后问题回溯算法的实现

void Backtrack(int t) {//形参t是回溯的深度，从1开始
　　int i;
　　//到达叶子结点，获得一个可行方案。累计总数，并输出该方案
　　if (t>n) {
　　　　sum++;		//是全局变量
　　　　for (i=1; i<=n; i++) 
　　　　　　printf(" %d", x[i]);
　　　　printf("\n");
　　}
　　else
　　　　for (i=1; i<=n; i++) {
　　　　　　x[t] = i;
　　　　　　if (Place(t)) Backtrack(t+1);
　　　　}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

检查当前皇后位置的约束函数

//形参t是回溯的深度
inline bool Place(int t) { 
　　int i; 
　　for (i=1; i<t; i++) 
　　　　if ((abs(t-i) == abs(x[i]-x[t])) || (x[i] == x[t]))  //同一条对角线；同一行
　　　　　　return false; 
　　return true; 
}
1
2
3
4
5
6
7
8