搜索
算法大作业电子工程学院A.实验内容在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，求解可以放置的方法种数。B.问题分析n后问题等于于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。即规定每一列放一个皇后，不会造成列上的冲突；当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态。C.算法设计1.解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第i个皇后占领了第j列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2.算法设计1/6因为n皇后问题，从n大于11开始求解过程耗时就很长，所以定义x数组的最大值MAXNUM=30；即最大可解决30皇后问题。1)判断当前位置是否可放置皇后皇后k在第k行第x[k]列时，x[i]==x[k]时，两皇后在同一列上;abs(x[i]-x[k])==abs(i-k)时，两皇后在同一斜线上;两种情况两皇后都可相互攻击，返回false表示不符合条件。boolPlace(intk){inti;i=1;while(ik){if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))returnfalse;i=i+1;}returntrue;2)输出当前解voidPrint(intx[],intn){num++;printf(第%d\t种解法:(,num);for(inti=1;i=n;i++){printf(%d,,x[i]);if(i%n==0)printf();\n);}3)回溯法搜索解空间voidNQueens(intn){intk=1;x[1]=0;while(k0){x[k]+=1;while(x[k]=n&&!Place(k))x[k]+=1;if(x[k]=n)2/6{if(k==n)Print(x,n);else{k=k+1;x[k]=0;}}//回溯至上一行；elsek--;}}3.实验结果及分析n皇后问题解的情况皇后的个数问题的解N=1X=(1)N=2无解N=3无解N=4X1=(2,4,1,3);X2=(3,1,4,2)N=5X1=(1,3,5,2,4);X2=(1,4,2,5,3);X3=(2,4,1,3,5);X4=(2,5,3,1,4)；X5=(3,1,4,2,5);X6=(3,5,2,4,1);X7=(4,1,3,5,2);X8=(4,2,5,3,1)；X9=(5,2,4,1,3);X10=(5,3,1,4,2)N=6X1=(2,4,6,1,3,5);X2=(3,6,2,5,1,4);X3=(4,1,5,2,6,3);X4=(5,3,1,6,4,2)N=740个解N=892个解4.实验程序随着N的增大，解的个数增多，以N=4为例#includestdio.h#includemath.h#defineN4/*定义棋盘大小*/staticintsum;/*当前已找到解的个数*/staticintx[N];intplace(intk){intj;for(j=0;jk;j++)if(x[j]==x[k]||abs(j-k)==abs(x[j]-x[k]))return0;3/6return1;}/*打印棋局*/voidchessboard(){inti,j;intsite[N];printf(第%d种解法:\n,++sum);for(i=0;iN;i++){for(j=0;jN;j++)if(j==x[i]){printf(Q);site[i]=j+1;}elseprintf(*);printf(\n);}printf(A%d(,sum);for(i=0;iN;i++){printf(%d,,site[i]);}printf(););printf(\n);}/*回溯搜索解空间*/voidbacktrack(){intk=0;x[0]=-1;while(k=0){x[k]+=1;/*向右移一列*//*向右移至出最右列或可以放置皇后的列*/while((x[k]N)&&!(place(k)))x[k]+=1;if(x[k]N)/*向右移未移出棋盘*/if(k==N-1)chessboard();/*已移至最后一行*/elsex[++k]=-1;/*向下移一行*/elsek--;/*回溯到上一行*/}}intmain(void){backtrack();printf(%d皇后有%d个解:\n,N,sum);return0;}4/6实验结果截图：5.流程图5/6D.心得体会通过算法老师布置的这次大作业，首先使我们更好地理解皇后问题和回溯法的原理；其次，在作业过程中遇到的困难，使我们3人学会了如何合作才能更高效的解决问题；最后，在这次作业中，锻炼了我们收集资料，学习新技能的能力，感谢老师！E.参考文献《算法设计技巧与分析》——电子工业出版社《C程序设计》——西安电子科技大学出版社《回溯法》——百度文库