n皇后问题算法设计.doc

《n皇后问题算法设计.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法设计及分析n皇后问题---回溯求解国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动；也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么，在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了部分解答。高斯在棋盘上放下了N个互不攻击的皇后，他还认为可能有N种不同的放法，这就是有名的“N皇后”问题。如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记忆有限，很可能在某个位置放过子后来证明不

2、行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法则才行。回溯法的基本思想：对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。不妨以8皇后为例，设8皇后为xi，她们分别

3、在第i行（i=1,2,3,4,5,6,7,8）,这样问题的解空间就是一个8个皇后所在列的序号，为n元一维向量（x1,x2,,x3,x4,x5,x6,x7,x8），搜索空间是1≤xi≤8（i=1,2,3,4,5,6,7,8）,共88个状态。约束条件是8个点（1,x1）,(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一列和同一对角线上。虽然问题共有88个状态，但算法不会真正地搜索这么多的状态，因为回溯法采用的是“走不通就掉头”的策略，而形如（1,1,x3,x4,x5,x6,x7,x8）的

4、状态共有86个，由于1,2号皇后在同一列不满足约束条件，回溯后这些状态是不会搜索的。算法设计：我们用三个数组c,b,d分别记录棋盘上的n个列，2n-1个住对角线和2n-1个副对角线的占用情况。用i,j分别表示皇后所在的行列，用表达式i-j+n对主对角线编号，范围是1～2n-1，用i+j为负对角线编号，范围为2～2n.程序代码：#include"stdio.h"inta[20],b[20],c[40],d[40],n,i,k;intt=0;//t记录解的个数voidoutput(){t=t+1;printf("第%d个解:",t);for(

5、k=1;k<=n;k++)printf("%d",a[k]);printf("");}voidfind(inti){intj;for(j=1;j<=n;j++)//第i个皇后有n种可能位置if(b[j]==0&&c[i+j]==0&&d[i-j+n]==0)//判断位置是否冲突{a[i]=j;//摆放皇后b[j]=1;//占领第j列c[i+j]=1;//占领两个对角线d[i-j+n]=1;if(i

6、+j]=0;d[i-j+n]=0;}}voidmain(){printf("皇后问题n=");scanf("%d",&n);for(i=1;i<=n;i++){b[i]=0;c[i]=0;d[i]=0;c[i+n]=0;d[i+n]=0;}find(1);}n=4时的运行结果：解的放置方式如图：n=6时的运行结果：解的放置方式如图：算法分析：数组b,c,d分别用来标记冲突。数组b代表列冲突，如果某列上已经有皇后，则为1，否则为0；数组c代表主对角线冲突，如果某条主对角线上已经有皇后，则为1，否则为0；数组d代表从对角线冲突，如果某条从对角

7、线上已经有皇后，则为1，否则为0。回溯法是一种满足某约束条件的穷举式搜索技术，适应于解决一些组合数相当大的问题。其优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。其程序编写相对复杂，且消耗很多的资源，但其实际情况较简单。递归是一种很古老的算法，其应用的也十分的广泛，在很多复杂的程序中也是经常性的使用，递归的优点是编写简单，缺点是消耗资源大。本程序采用回溯算法和递归，把八皇后问题的调用函数融合到了一个函数中。其时间复杂度为O(n2)。程序设计感想：通过对n皇后问题的算法设计及分析，我们对回溯算法和递归有

8、了更深的理解，提高我们程序设计、分析和理解问题的能力，加强了动手能力，增加编程的经验。