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

《回溯法解决n皇后问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、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-78皇后问题的一个解为了简单起见，图5-8只给出了n=4时问题的一种可能树结构。图5-84皇后问题解空间的树结构在实际中，并不需

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，且路径

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

5、表示问题的解，其中xi表示第i个皇后放在第i行所在的列数。由于不存在两个皇后位于同一列上，因此xi互不相同。设有两个皇后分别位于棋盘(i，j)和(k，l)处，如果两个皇后位于同一对角线上，这表明它们所在的位置应该满足：i-j=k-l或i+j=k+l。这两个等式表明，这两个皇后位于主对角线上或次对角线上。综合这两个等式可得，如果两个皇后位于同一对角线上，那么它们的位置关系一定满足

6、j-l

7、=

8、i-k

9、。3、搜索解空间树解n后问题的回溯算法可描述如下：求解过程从空配置开始。在第1列~的m列为合理配置的基础上，再配置第m+1列，直至第n列也是合理

10、时，就找到了一个解。在每列上，顺次从第一行到第n行配置，当第n行也找不到一个合理的配置时，就要回溯，去改变前一列的配置。用ｎ元组x[1:n]表示ｎ皇后问题的解，x[i]表示皇后i放在第i行的第x[i]列上，用完全ｎ叉树表示解空间。剪枝函数设计：对于两个皇后A(i，j)、B(k，l)两个皇后不同行：i不等于k;两个皇后不同列：j不等于l;两个皇后不同一条斜线

11、i-k

12、≠

13、j-l

14、，即两个皇后不处于同一条y=x+a或y=-x+a的直线上（1）、递归回溯下面的解n后问题的回溯法中，递归方法queen（1）实现对整个解空间的回溯搜索。queen（i

15、）搜索解空间中第i层子树。类Queen的数据成员记录解空间中结点信息，以减少传给queen的参数。sum记录当前已找到的可行方案数。在算法queen中，当i>n时，算法搜索到叶子结点，得到一个新的n皇后互不攻击放置方案，当前已找到的可行方案数sum加1.当in时，当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1.2，…，n，共n个儿子结点。对当前扩展结点Z的每一个儿子结点，由place检查其可行性，并以深度优先的方式递归地对可行子树搜索，或剪去不可行子树。算法5.7解N后问题的递归回溯算法classQueen{private:int

16、n;//皇后个数intsum=0;//可行解个数intx[N];//皇后放置的列数intplace(intk);intqueen(intt);}/*功能：判断函数，判断第k个皇后