回朔法与n皇后问题

发表于 | 分类于 | 阅读次数

回溯法

回溯法是应既带有系统性有带有跳跃性的搜索算法。它在包含问题的所有解的空间树中，按照深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时要回溯到根，且根结点的所有子树都已被搜索遍才结束；而用来求问题的任一解时。只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的方法称为回溯法。

在应用回溯法解决问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。在确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前的扩展结点。如果在当前 扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应回溯（往回移动）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直到找到所要求的解或解空间中已无活结点为止。

n皇后问题

n皇后问题来源于国际象棋的一个问题。n皇后问题要求在一个n × n 格的棋盘上放置n个皇后，使得他们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的任何棋子。因此，n皇后问题等价于在一个n × n 格的棋盘上放置n个皇后，使得任意两个皇后不能被放在同一行或同一列或同一斜线上。

求解过程从空棋盘开始，设在第1行至第m行都正确的放置了m个皇后，再在第m+1行上找合适的位置放置第m+1个皇后，直到在第n行也找到合适的位置放置第n个皇后，就找到了一个解。接着改变第n行上皇后的位置，希望获得下一个解。另外，在任一行上有n种可能的位置。开始时位置在第1列，以后改变时，顺次选择第2列、第3列…、第n列。当n列也不是一个合理的位置时，就要回溯，去改变前一行的位置。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdio.h>
#include <math.h>
#define N 4

/************************************************************************/
/* pos:一维数组，pos[i]表示第i个皇后放在第i行的具体位置                 */
/* count:统计放置的方案数                                               */
/* N:皇后数                                                             */
/* i,j,k:变量                                                           */
/************************************************************************/

/*判断第k个皇后是否与前面皇后冲突*/
int IsPlase(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, 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;
		/*尝试摆放第j个皇后*/
		while (pos[j] <= N && IsPlase(pos,j)==0)
		{
			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 = j + 1;
		} 
		else
		{
			pos[j] = 0;
			j = j - 1;
		}
	}
	return 0;
}