文档介绍：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-78皇后问题的一个解为了简单起见,图5-8只给出了n=4时问题的一种可能树结构。图5-84皇后问题解空间的树结构在实际中,并不需要生成问题的整个状态空间。通过使用限界函数来删除那些还没有生成其所有子结点的活结点。如果用(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--9具有限界函数的4皇后问题的状态空间树24133142图5-104皇后问题的解图示很容易就可将8皇后问题推广到n皇后问题(n-queenproblem),即找出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行也找不