回溯法解决n皇后问题.doc

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)表示皇后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皇后问题解空间的树结构 在实际中，并不需要生成问题的整个状态空间。通过使用限界函数来删除那些还没有生成其所有子结点的活结点。 如果用(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也被杀死。回溯到结点2，生成它的下一个结点13， 且路径变为(1， 4)。图5-8表示4皇后问题回溯时的状态空间树。图中一个结点一旦被限界函数杀死，则用B做上记号，如图5-9所示。 4皇后问题的解结果如5-10所示. B B 图 5-9 具有限界函数的4皇后问题的状态空间树 2 4 1 3 3 1 4 2 图5-10 4皇后问题的解图示 很容易就可将8皇后问题推广到n皇后问题(n-queen problem)，即找出n×n的棋盘上放置n个皇后并使其不能互相攻击的所有解。设X =(x1， x2， …， xn)表示问题的解，其中xi表示第i个皇后放在第i行所在的列数。由于不存在两个皇后位于同一列上， 因此xi互不相同。设有两个皇后分别位于棋盘(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行也找不到一个合理的配置时，就要回溯，去改变前一列的配置。 用ｎ元组x[1:n]表示ｎ皇后问题的解，x[i]表示皇后i放在第i 行的第x[i]列上，用完全ｎ叉树表示解空间。 剪枝函数设计：对于两个皇后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中，当in时，算法搜索到叶子结点，得到一个新的n皇后互不攻击放置方案，当前已找到的可行方案数sum加1. 当in时，当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1.2，…，n