皇后问题
N皇后问题，是一个古老而著名的问题，是回溯算法的典型例题：在NN格的格子上
摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜
线上，问有多少种摆法？
1、定义问题的解空间
首先以八皇后为例，可以用一棵树表示8皇后问题的解空间。由于8皇后问题的解空
间为8种排列，因此我们将要构造的这棵树实际上是一棵排列树。
2、确定解空间树的结构
给棋盘上的行和列从1到8编号，同时也给皇后从1到8编号。由于每一个皇后应放在
不同的行上，不失一般性，假设皇后i放在第i行上，因此8皇后问题可以表示成8元组x1，x2，…，x8，其中xii1，2，…，8表示皇后i所放置的列号。这种表示法的显式约束条件是Si1，2，3，4，5，6，7，8，i1，2，…，8。在这种情况下，解空间为88个8元组组成，而隐式约束条件是没有两个xi相同即所有皇后必须在不同列上，
且满足不存在两个皇后在同一条对角线上。加上隐式约束条件，问题的解空间可进一步减小。
此时，解空间大小为8，因为所有解都是8元组的一个置换。图57表示了8皇后问题的
一个解。
12345678
1
Q
2
Q
3
Q
4
Q
5
Q
6Q
7
Q
8
Q
图578皇后问题的一个解为了简单起见，图58只给出了
4时问题的一种可能树结构。
1
1
2
3
4
2234
18134
34
12
4
50
12
3
3
8
13
19
24
29
35
40
45
51
56
61
342423341413241412231312
469111416202225273032363841434648525457596264434232434131424121323121
5710121517212326283133373942444749535558606365
f图584皇后问题解空间的树结构在实际中，并不需要生成问题的整个状态空间。通过使用限界函数来删除那些还没有生成其所有子结点的活结点。如果用x1，x2，…，xi表示到当前E结点的路径，那么xi1就是这样的一些结点，它使得x1，x2，…，xi，xi1没有两个皇后处于相互攻击的棋盘格局。在4皇后问题中，惟一开始结点为根结点1，路径为。开始结点既是一个活结点，又是一个E结点，它按照深度优先的方式生成一个新结点2，此时路径为1，这个新结点2变成一个活结点和新的E结点，原来的E结点1仍然是一个活结点。结点2生成结点3，但立即被杀死。于是，回溯到结点2，生成它的下一个结点8，且路径变为1，3。结点8成为E结点，由于它的所有子结点不可能导致答案结点，因此结点8也被杀死。回溯到结点2，生成它的下一个结点13，且路径变为1，4。图58表示4皇后问题回溯时的状态r