搜索技术【深度优先搜索】 - 排列树

搜索技术【深度优先搜索】 - 排列树

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

如果棋盘如下图所示，

我们在第i 行第j 列放置一个皇后，那么第i 行的其他位置（同行）、第j 列的其他位置（同列）、同一斜线上的其他位置，都不能再放置皇后。

不可能杂乱无章地尝试每个位置，需要有策略地求解，可以以行为主导。

① 在第1行第1列放置第1个皇后。

② 在第2行放置第2个皇后。第2个皇后的位置不能与第1个皇后同列、同斜线，不用再判断是否同行，因为每行只放置一个，本来就已经不同行。

③ 在第3行放置第3个皇后，第3个皇后的位置不能与前2个皇后同列、同斜线。

④ …

⑤ 在第t行放置第t个皇后，第t个皇后的位置不能与前t-1个皇后同列、同斜线。

⑥ …

⑦ 在第n 行放置第n 个皇后，第n 个皇后的位置不能与前n -1个皇后同列、同斜线。

【算法设计】

[1] 定义问题的解空间。n 皇后问题的解的形式为n 元组：{x 1,x 2 ,…,xi ,…,xn }，分量xi 表示第i 个皇后被放置在第i 行第xi列，xi 的取值为1,2,…,n 。例如x 2 =5，表示第2个皇后被放置在第2行第5列。显约束为不同行。

[2] 解空间的组织结构。n 皇后问题的解空间是一棵m （m =n ）叉树，树的深度为n ，如下图所示。

[3] 搜索解空间。

• 约束条件。在第t 行放置第t 个皇后时，第t 个皇后的位置不能与前t -1个皇后同列、同斜线。第i 个皇后与第j 个皇后不同列，即xi!=xj ，并且不同斜线|i -j | != |xi -xj |。
• 限界条件。该问题不存在放置方案是否好坏的情况，所以不需要设置限界条件。
• 搜索过程。从根开始，以深度优先搜索的方式进行搜索。根节点是活节点并且是当前扩展节点。在搜索过程中，当前扩展节点沿纵深方向移向一个新节点，判断该新节点是否满足隐约束，如果满足，则新节点成为活节点，并且成为当前扩展节点，继续深一层的搜索，如果不满足，则换到该新节点的兄弟节点继续搜索；如果新节点没有兄弟节点，或其兄弟节点已全部搜索完毕，则扩展节点成为死节点，搜索回溯到其父节点处继续进行。搜索到问题的根节点变成死节点时为止。

【举个栗子】

在4×4的棋盘上放置4个皇后，使其彼此不受攻击。

① 开始搜索第1层（t =1）。扩展节点1，判断x 1 =1是否满足约束条件，因为之前还未选中任何节点，满足约束条件。令x [1]=1，生成节点2。

② 扩展节点2（t =2）。判断x 2 =1不满足约束条件，因为与之前放置的第1个皇后同列；考察x 2 =2也不满足约束条件，因为与之前放置的第1个皇后同斜线；考察x 2 =3满足约束条件，因为与之前放置的皇后不同列、不同斜线，令x [2]=3，生成节点3。

③ 扩展节点3（t =3）。判断x 3 =1不满足约束条件，因为与之前放置的第1个皇后同列；考察x 3 =2也不满足约束条件，因为与之前放置的第2个皇后同斜线；考察x 2 =3不满足约束条件，因为与之前放置的第2个皇后同列；考察x 3 =4也不满足约束条件，因为与之前放置的第2个皇后同斜线；对节点3的所有孩子均已考察完毕，节点3成为死节点。向上回溯到节点2。

④ 重新扩展节点2（t =2）。判断x 2 =4满足约束条件，因为与之前放置的第1个皇后不同列、不同斜线，令x [2]=4，生成节点4。

⑤ 扩展节点4（t =3）。判断x 3 =1不满足约束条件，因为与之前放置的第1个皇后同列；考察x 3 =2满足约束条件，因为与之前放置的第1、2个皇后不同列、不同斜线，令x [3]=2，生成节点5。

⑥ 扩展节点5（t =4）。判断x 4 =1不满足约束条件，因为与之前放置的第1个皇后同列；考察x 4 =2也不满足约束条件，因为与之前放置的第3个皇后同列；考察x 4 =3不满足约束条件，因为与之前放置的第3个皇后同斜线；考察x 4 =4也不满足约束条件，因为与之前放置的第2个皇后同列；对节点5的所有孩子均已考察完毕，节点5成为死节点。向上回溯到节点4。

⑦ 继续扩展节点4（t =3）。判断x 3 =3不满足约束条件，因为与之前放置的第2个皇后同斜线；考察x 3 =4也不满足约束条件，因为与之前放置的第2个皇后同列；节点4的所有孩子均已考察完毕，节点4成为死节点。向上回溯到节点2。对节点2的所有孩子均已考察完毕，节点2成为死节点。向上回溯到节点1。

⑧ 继续扩展节点1（t =1）。判断x 1 =2是否满足约束条件，因为之前还未选中任何节点，满足约束条件。令x [1]=2，生成节点6。

⑨ 扩展节点6（t =2）。判断x 2 =1不满足约束条件，因为与之前放置的第1个皇后同斜线；考察x 2 =2也不满足约束条件，因为与之前放置的第1个皇后同列；考察x 2 =3不满足约束条件，因为与之前放置的第1个皇后同斜线；考察x 2 =4满足约束条件，因为与之前放置的第1个皇后不同列、不同斜线，令x [2]=4，生成节点7。

⑩ 扩展节点7（t =3）。判断x 3 =1满足约束条件，因为与之前放置的第1、2个皇后不同列、不同斜线，令x [3]=1，生成节点8。

⑪ 扩展节点8（t =4）。判断x 4 =1不满足约束条件，因为与之前放置的第3个皇后同列；考察x 4 =2也不满足约束条件，因为与之前放置的第1个皇后同列；考察x 4 =3满足约束条件，因为与之前放置的第1、2、3个皇后不同列、不同斜线，令x [4]=3，生成节点9。

⑫ 扩展节点9（t =5）。t >n ，找到一个可行解，用bestx[]保存当前可行解{2,4,1,3}。节点9成为死节点。向上回溯到节点8。

⑬ 继续扩展节点8（t =4）。判断x 4 =4不满足约束条件，因为与之前放置的第2个皇后同列；对节点8的所有孩子均已考察完毕且成为死节点。向上回溯到节点7。

⑭ 继续扩展节点7（t =3）。判断x 3 =2不满足约束条件，因为与之前放置的第1个皇后同列；判断x 3 =3不满足约束条件，因为与之前放置的第2个皇后同斜线；判断x 3 =4不满足约束条件，因为与之前放置的第2个皇后同列；对节点7的所有孩子均已考察完毕成为死节点。向上回溯到节点6。节点6的所有孩子均已考察完毕并成为死节点。向上回溯到节点1。

⑮ 继续扩展节点1（t =1）。判断x 1 =3是否满足约束条件，因为之前还未选中任何节点，满足约束条件。令x [1]=3，生成节点10。

⑯ 扩展节点10（t =2）。判断x 2 =1满足约束条件，因为与之前放置的第1个皇后不同列、不同斜线，令x [2]=1，生成节点11。

⑰ 扩展节点11（t =3）。判断x 3 =1不满足约束条件，因为与之前放置的第2个皇后同列；考察x 3 =2也不满足约束条件，因为与之前放置的第2个皇后同斜线；考察x 3 =3不满足约束条件，因为与之前放置的第1个皇后同列；考察x 3 =4满足约束条件，因为与之前放置的第1、2个皇后不同列、不同斜线，令x [3]=4，生成节点12

⑱ 扩展节点12（t =4）。判断x 4 =1不满足约束条件，因为与之前放置的第2个皇后同列；考察x 4 =2满足约束条件，因为与之前放置的第1、2、3个皇后不同列、不同斜线，令x [4]=2，生成节点13。

⑲ 扩展节点13（t =5）。t >n ，找到一个可行解，用bestx[]保存当前可行解{3,1,4,2}。节点13成为死节点。向上回溯到节点12。

⑳ 继续扩展节点12（t =4）。判断x 4 =3不满足约束条件，因为与之前放置的第1个皇后同列；判断x 4 =4不满足约束条件，因为与之前放置的第3个皇后同列；对节点12的所有孩子均已考察完毕并成为死节点。向上回溯到节点11。对节点11的所有孩子均已考察完毕并成为死节点。向上回溯到节点10。

㉑ 继续扩展节点10（t =2）。判断x 2 =2不满足约束条件，因为与之前放置的第1个皇后同斜线；判断x 2 =3不满足约束条件，因为与之前放置的第1个皇后同列；判断x 2 =4不满足约束条件，因为与之前放置的第1个皇后同斜线；对节点10的所有孩子均已考察完毕并成为死节点，向上回溯到节点1。

㉒ 继续扩展节点1（t =1）。判断x 1 =4是否满足约束条件，因为之前还未选中任何节点，满足约束条件。令x [1]=4，生成节点14。

㉓ 扩展节点14（t =2）。判断x 2 =1满足约束条件，因为与之前放置的第1个皇后不同列、不同斜线，令x [2]=1，生成节点15。

㉔ 扩展节点15（t =3）。判断x 3 =1不满足约束条件，因为与之前放置的第2个皇后同列；考察x 3 =2也不满足约束条件，因为与之前放置的第2个皇后同斜线；考察x 3 =3满足约束条件，因为与之前放置的第1、2个皇后不同列、不同斜线，令x [3]=3，生成节点16。

㉕ 扩展节点16（t =4）。判断x 4 =1不满足约束条件，因为与之前放置的第2个皇后同列；考察x 4 =2也不满足约束条件，因为与之前放置的第3个皇后同斜线；考察x 4 =3不满足约束条件，因为与之前放置的第3个皇后同列；考察x 4 =4也不满足约束条件，因为与之前放置的第1个皇后同列；对节点16的所有孩子均已考察完毕并成为死节点。向上回溯到节点15。

㉖ 继续扩展节点15（t =3）。判断x 3 =4不满足约束条件，因为与之前放置的第1个皇后同列；对节点15的所有孩子均已考察完毕并成为死节点。向上回溯到节点14。

㉗ 继续扩展节点14（t =2）。判断x 2 =2满足约束条件，因为与之前放置的第1个皇后不同列、不同斜线，令x [2]=2，生成节点17。

㉘ 扩展节点17（t =3）。判断x 3 =1不满足约束条件，因为与之前放置的第2个皇后同斜线；考察x 3 =2也不满足约束条件，因为与之前放置的第2个皇后同列；考察x 3 =3不满足约束条件，因为与之前放置的第2个皇后同斜线；考察x 3 =4也不满足约束条件，因为与之前放置的第1个皇后同列；对节点17的所有孩子均已考察完毕并成为死节点。向上回溯到节点14。

㉙ 继续扩展节点14（t =2）。判断x 3 =3不满足约束条件，因为与之前放置的第2个皇后同斜线；判断x 3 =4不满足约束条件，因为与之前放置的第1个皇后同列；对节点14的所有孩子均已考察完毕并成为死节点。向上回溯到节点1。

㉚ 对节点1的所有孩子均已考察完毕并成为死节点，算法结束

【算法实现】

① 约束函数。在第t 行放置第t 个皇后时，第t 个皇后与前t-1个已放置好的皇后不能同列或同斜线。如果有一个成立，则第t 个皇后不可以被放置在该位置。x [t ]==x [j ]表示第t 个皇后与第j 个皇后同列，t -j ==abs(x [t ]-x [j ])表示第t 个皇后与第j 个皇后同斜线。abs是求绝对值的函数，使用该函数时要引入头文件#include。

bool check(){ //判断第t 个皇后能否被放置在第 i个位置
	for(int j = 1; j < t ; j++){ // 判断该位置的皇后是否与前面t-1 个已被放置的皇后冲突
		if((x[t] == x[j]) || (t - j == abs(x[t] - x[j]))){ //判断列、对角线是否冲突
			return false;
		}
	}
	return true;
}
1
2
3
4
5
6
7
8

② 按约束条件搜索求解。t 表示当前扩展节点在第t 层。如果t>n ，则表示已经到达叶子节点，记录最优值和最优解，返回。否则，分别判断n (i =1…n )个分支，x [t ]=i ；判断每个分支是否满足约束条件，如果满足，则进入下一层Backtrack(t +1)，否则考察下一个分支（兄弟节点）。

void Backtrack(int t){
	if(t > n){ //如果到达叶子节点，则表示已经找到了问题的一个解
		ans ++;
		for(int i = 1; i <= n ; i++){ //输出可行解
			cout << x[i] << " ";
		}
		cout << endl;
	}
	else{
		for(int i = 1 ; i <= n ; i ++){ //不要将i 定义为全局变量，否则递归调用有问题
			x[t] = i;
			if(check(t)){
				Backtrack(t + 1); //如果不冲突，则进行下一行的搜索
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

【算法分析】

时间复杂度： 在最坏情况下，解空间树如下图所示。除了最后一层，有1+n +n^2 +…+n^n -1 = (n^n -1)/(n -1)≈n^n -1 个节点需要扩展，而这些节点的每一个都要扩展n 个分支，总的分支个数为n^n ，每个分支都判断约束函数，判断约束条件需要O (n )时间，因此耗时O (n^n +1)。在叶子节点处输出当前最优解需要耗时O (n )，在最坏情况下会搜索到每一个叶子节点，叶子个数为n^n ，故耗时O (n^(n +1) )。因此，时间复杂度为O (n^(n +1) )。

空间复杂度： 回溯法的另一个重要特性就是在搜索执行的同时产生解空间。在搜索过程中的任何时刻，仅保留从开始节点到当前扩展节点的路径，从开始节点起最长的路径为n 。在程序中使用x []数组记录该最长路径作为可行解，所以该算法的空间复杂度为O (n )。

【算法优化】

在上面的求解过程中，我们的解空间过于庞大，所以时间复杂度很高，算法效率当然会降低。解空间越小，算法效率越高。

那么能不能把解空间缩小呢？

n 皇后问题要求每一个皇后都不同行、不同列、不同斜线。上图所示的解空间使用了不同的行作为显约束。隐约束为不同列、不同斜线。对4皇后问题，显约束为不同行的解空间树如下图所示。

显约束可以控制解空间大小，隐约束是在搜索解空间过程中判定可行解或最优解的。如果我们把显约束定为不同行、不同列，把隐约束定义为不同斜线，那么解空间是怎样的呢？

例如x 1 =1的分支，x 2 就不能再等于1，因为这样就同列了。如果x=1，x 2 =2，x 3 就不能再等于1、2。也就是说，xt 的值不能与前t -1个解的取值相同。每层节点产生的孩子数都比上一层少1。4皇后问题，显约束为不同行、不同列的解空间树如下图所示。

我们可以清楚地看到解空间变小许多，仔细观察就会发现，上图中，从根到叶子的每一个可能解其实都是一个排列，该解空间树是一棵排列树。使用排列树求解n 皇后问题的代码如下。

void Backtrack(int t){
	if(t > n){
		ans ++;
		return;
	}
	
	for(int i = t; i <= n ; i++){
		swap(x[t] , x[i]); //通过交换得到全排列
		if(check(t)){
			Backtrack(t + 1); 
		}
		swap(x[t] , x[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14