回溯法解决n皇后问题

1、n 皇 后 问 题N皇后问题，是一个古老而著名的问题，是回溯算法的典型例题：在N*N格的格子上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？1、定义问题的解空间首先以八皇后为例，可以用一棵树表示8皇后问题的解空间。 由于8皇后问题的解空间为8!种排列，因此我们将要构造的这棵树实际上是一棵排列树。2、确定解空间树的结构给棋盘上的行和列从1到8编号，同时也给皇后从1到8编号。由于每一个皇后应放在不同的行上，不失一般性，假设皇后i放在第i行上，因此8皇后问题可以表示成8元组(x1， x2， ， x8)， 其中xi(i=1， 2， ， 8)表示皇后

2、i所放置的列号。这种表示法的显式约束条件是Si=1， 2， 3， 4， 5， 6， 7， 8，i=1， 2， ， 8。在这种情况下， 解空间为88个8元组组成，而隐式约束条件是没有两个xi相同(即所有皇后必须在不同列上)，且满足不存在两个皇后在同一条对角线上。加上隐式约束条件，问题的解空间可进一步减小。此时，解空间大小为8!，因为所有解都是8元组的一个置换。图5-7表示了8皇后问题的一个解。 图5-7 8皇后问题的一个解为了简单起见，图5-8只给出了n=4时问题的一种可能树结构。图 5-8 4皇后问题解空间的树结构在实际中，并不需要生成问题的整个状态空间。通过使用限界函数来删除那些还没有生成其

3、所有子结点的活结点。 如果用(x1， x2， ， xi)表示到当前E结点的路径，那么xi+1就是这样的一些结点，它使得(x1， x2， ， xi， xi+1)没有两个皇后处于相互攻击的棋盘格局。 在4皇后问题中，惟一开始结点为根结点1，路径为( )。开始结点既是一个活结点，又是一个E结点， 它按照深度优先的方式生成一个新结点2，此时路径为(1)，这个新结点2变成一个活结点和新的E结点， 原来的E结点1仍然是一个活结点。结点2生成结点3，但立即被杀死。于是，回溯到结点2，生成它的下一个结点8，且路径变为(1， 3)。 结点8成为E结点，由于它的所有子结点不可能导致答案结点， 因此结点8也被杀死。

4、回溯到结点2，生成它的下一个结点13， 且路径变为(1， 4)。图5-8表示4皇后问题回溯时的状态空间树。图中一个结点一旦被限界函数杀死，则用B做上记号，如图5-9所示。4皇后问题的解结果如5-10所示. B B图 5-9 具有限界函数的4皇后问题的状态空间树24133142 图5-10 4皇后问题的解图示 很容易就可将8皇后问题推广到n皇后问题(n-queen problem)，即找出n×n的棋盘上放置n个皇后并使其不能互相攻击的所有解。设X =(x1， x2， ， xn)表示问题的解，其中xi表示第i个皇后放在第i行所在的列数。由于不存在两个皇后位于同一列上， 因此xi互不相同。

5、设有两个皇后分别位于棋盘(i， j)和(k， l)处， 如果两个皇后位于同一对角线上，这表明它们所在的位置应该满足： i-j=k-l或i+j=k+l。这两个等式表明，这两个皇后位于主对角线上或次对角线上。综合这两个等式可得，如果两个皇后位于同一对角线上，那么它们的位置关系一定满足|j-l|=| i-k|。 3、搜索解空间树解n后问题的回溯算法可描述如下：求解过程从空配置开始。在第1列的m列为合理配置的基础上，再配置第m+1列，直至第n列也是合理时，就找到了一个解。在每列上，顺次从第一行到第n行配置，当第n行也找不到一个合理的配置时，就要回溯，去改变前一列的配置。用元组x1:n表示皇后问题的解，

6、xi表示皇后i放在第i 行的第xi列上，用完全叉树表示解空间。剪枝函数设计：对于两个皇后A(i，j)、B(k，l)两个皇后不同行：i不等于k;两个皇后不同列：j不等于l;两个皇后不同一条斜线|i-k|j-l|，即两个皇后不处于同一条y=x+a或y=-x+a的直线上（1）、递归回溯下面的解n后问题的回溯法中，递归方法queen（1）实现对整个解空间的回溯搜索。queen（i）搜索解空间中第i层子树。类Queen的数据成员记录解空间中结点信息，以减少传给queen的参数。sum记录当前已找到的可行方案数。在算法queen中，当i>n时，算法搜索到叶子结点，得到一个新的n皇后互不攻击放置方案，

7、当前已找到的可行方案数sum加1.当in时，当前扩展结点Z是解空间中的内部结点。该结点有xi=1.2，n，共n个儿子结点。对当前扩展结点Z的每一个儿子结点，由place检查其可行性，并以深度优先的方式递归地对可行子树搜索，或剪去不可行子树。算法 5.7 解N后问题的递归回溯算法class Queenprivate:int n; /皇后个数 int sum = 0; /可行解个数 int xN; /皇后放置的列数 int place(int k); int queen(int t);/*功能：判断函数，判断第k个皇后是否可以放在某一个位置。 输入：第k个皇后。 输出：如果与之前的皇后出现在同一列

8、或同一对角线则放置失败，返回0，否则返1。*/int Queen :place(int k) int i; for(i=1;i<k;i+) if(abs(k-i)=abs(xk-xi) | xk = xi) return 0; return 1; /* 功能：求解可行解函数。当第t个皇后可以放置在t行的某一位置时，继续放置下一皇后，直到 所有皇后放置结束，如果某一皇后不能放置，则移向下一列放置，如果这一列都不能放置或所有皇后放置结束，返回上一皇后重新放置，最终返回所有可行解个数。 输入：第t个皇后。 输出：可行解个数。*/int Queen:queen(int t) if(t>n

9、&& n>0) /当放置的皇后超过n时，可行解个数加1，此时n必须大于0 sum+; else for(int i=1;i<=n;i+) xt = i; /标明第t个皇后放在第i列 if(place(t) /如果可以放在某一位置，则继续放下一皇后 queen(t+1); return sum; （2）、迭代回溯数组x记录了解空间树中从根到当前扩展结点的路径，这些信息已包含了回溯法在回溯时所需要的信息。利用数组x所含信息，可将上述回溯法表示成非递归形式，进一步省去O（n）递归栈空间。算法 5.8 解N后问题的非递归迭代回溯算法/* 功能：求解可行解函数。 输入：无输出：可行解个数。*/int Queen:queen() x1 = 0; int