N皇后问题实验报告

1、算法大作业电子工程学院A.实验内容在nx n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规 则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，求解可以 放置的方法种数。B.问题分析n后问题等于于在nxn格的棋盘上放置n个皇后，任何2个皇后不放 在同一行或同一列或同一斜线上。即规定每一列放一个皇后，不会造成列 上的冲突；当第i行被某个皇后占领后，则同一行上的所有空格都不能再 放皇后，要把以i为下标的标记置为被占领状态。C.算法设计1 .解决冲突问题：这个问题包括了行，歹I，两条对角线；歹|：规定每一列放一个皇后，不会造成列上的冲突；行：当第i行被某个皇后占领后，则同一行上的所有空

2、格都不能再放皇后，要把以i为下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为（i,j），要么（i+j）是常数， 要么（i-j）是常数。因此，当第i个皇后占领了第j列后，要同时把以（i+j）、 （i-j）为下标的标记置为被占领状态。2 .算法设计因为 n 皇后问题，从n 大于 11 开始求解过程耗时就很长，所以定义x数组的最大值MAXNUM= 3013最大可解决30皇后问题。1) 判断当前位置是否可放置皇后皇后 k 在第 k 行第 xk 列时， xi=xk 时，两皇后在同一列上 ;abs(xi-xk)=abs(i-

3、k) 时，两皇后在同一斜线上; 两种情况两皇后都可相互攻击，返回false 表示不符合条件。bool Place(int k)int i;i=1;while(i<k)if(xi=xk|abs(xi-xk)=abs(i-k) return false;i=i+1;return true;2) 输出当前解void Print(int x,int n)num+;printf(" 第 %dt 种解法 :(",num);for(int i=1;i<=n;i+)printf("%d,",xi);if(i%n=0)printf(");n"

4、;);3) 回溯法搜索解空间void NQueens(int n)int k=1;x1=0;while(k>0)xk+=1;while(xk<=n&&!Place(k)xk+=1;if(xk<=n)if(k=n)Print(x,n); else k=k+1;xk=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

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为例 #include <stdio.h>#include<math.h>#define N 4 /*定义棋盘大小*/static int sum; /*

6、当前已找到解的个数*/static int xN;int place(int k)int j;for (j = 0; j < k; j +)if (xj = xk | abs(j - k) = abs(xj - xk) return 0;return 1;/* 打印棋局*/void chessboard()int i,j;int siteN;printf("第由中解法:n", + sum);for (i = 0; i < N; i +) for (j = 0; j < N; j +)if (j = xi) printf("Q ");si

7、tei=j+1; else printf("* ");printf("n");printf("A%d(",sum);for(i = 0; i < N; i +)printf("%d,",sitei);printf(");");printf("n");/* 回溯搜索解空间*/void backtrack()int k = 0;x0 = -1;while (k >= 0) xk += 1; /*向右移一列*/* 向右移至出最右列或可以放置皇后的列*/while (xk < N) && !(place(k) xk += 1;if (xk < N) /*向右移未移出棋盘*/if (k = N - 1) chessboard(); /*已移至最后一行 */else x+ k = -1; /*向下移一行*/else k -; /*回溯到上一行*/int main(void)backtrack();printf("%d皇后有 d 个解:n",N,sum);return 0;5/ 6实验结果截图:5.流程图从n到珏绽霹意电2匹三亶rJD.心得体会通过算法老师布置的这次大作业，首先使我们更好地理解皇后问题和回溯