皇后冲突
ktv游戏-二次配
2023年3月19日发(作者：劳动法赔偿)N皇后问题实验报告
电子工程学院
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.算法设计
因为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(i { if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k)) returnfalse; i=i+1; } returntrue; 2)输出当前解 voidPrint(intx[],intn){ num++; printf("第%dt种解法:(",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(k>0) { x[k]+=1; while(x[k]<=n&&!Place(k)) x[k]+=1; if(x[k]<=n) 1/6 { if(k==n) Print(x,n); else { k=k+1; x[k]=0; } } //回溯至上一行; else k--; } } 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=6 X1=(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为例 #include #include #defineN4/*定义棋盘大小*/ staticintsum;/*当前已找到解的个数*/ staticintx[N]; intplace(intk) { intj; for(j=0;j if(x[j]==x[k]||abs(j-k)==abs(x[j]-x[k])) return0; 2/6 return1; } /*打印棋局*/ voidchessboard() { inti,j; intsite[N]; printf("第%d种解法:n",++sum); for(i=0;i for(j=0;j if(j==x[i]){printf("Q");site[i]=j+1;} elseprintf("*"); printf("n"); } printf("A%d(",sum); for(i=0;i { printf("%d,",site[i]); } printf(");"); printf("n"); } /*回溯搜索解空间*/ voidbacktrack() { intk=0; x[0]=-1; while(k>=0){ x[k]+=1;/*向右移一列*/ /*向右移至出最右列或可以放置皇后的列*/ while((x[k] if(x[k] if(k==N-1)chessboard();/*已移至最后一 行*/ elsex[++k]=-1;/*向下移一行*/ elsek--;/*回溯到上一行*/ } } intmain(void) { backtrack(); printf("%d皇后有%d个解:n",N,sum); return0; } 3/6 实验结果截图: 5.流程图 4/6 D.心得体会 通过算法老师布置的这次大作业，首先使我们更好地理解皇后问题和回溯法的 原理;其次，在作业过程中遇到的困难，使我们3人学会了如何合作才能更高效的 解决问题;最后，在这次作业中，锻炼了我们收集资料，学习新技能的能力，感谢 老师～ E.参考文献 《算法设计技巧与分析》——电子工业出版社 《C程序设计》——西安电子科技大学出版社 《回溯法》——百度文库 5/6