N皇后问题实验报告总结计划.docx

算法大作业 电子工程学院 实验内容 在 n× n 格的棋盘上放置彼此不受攻击的 n 个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，求解可以放置的方法种数。 问题分析 n 后问题等于于在 n× n 格的棋盘上放置 n 个皇后，任何 2 个皇后不放在同一行或同一列或同一斜线上。即规定每一列放一个皇后，不会造成列 上的冲突；当第 i 行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以 i 为下标的标记置为被占领状态。 算法设计 解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第 i 行被某个皇后占领后，则同一行上的所有空格都不能再放皇 后，要把以 i 为下标的标记置为被占领状态； 对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和 从对角线。在同一对角线上的所有点 （设下标为 (i,j) ），要么 (i+j) 是常数， 要么 (i-j) 是常数。因此，当第 i 个皇后占领了第 j 列后，要同时把以 (i+j) 、 (i-j) 为下标的标记置为被占领状态。 2. 算法设计 因为 n 皇后问题，从 n 大于 11 开始求解过程耗时就很长，所以定义 x 数组的最大值 MAXNUM=30；即最大可解决 30 皇后问题。 判断当前位置是否可放置皇后 皇后 k 在第 k 行第 x[k] 列时， x[i]==x[k] 时，两皇后在同一列 上;abs(x[i]-x[k])==abs(i-k) 时，两皇后在同一斜线上 ; 两种情况两皇后都可相互攻击，返回 false 表示不符合条件。 bool Place(int k) { int i; i=1; while(ik) { if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k)) return false; i=i+1; } return true; 输出当前解 void Print(int x[],int n) { num++; printf( 第%d\t 种解法 :(,num); for(int i=1;i=n;i++) { printf(%d,,x[i]); if(i%n==0)printf();\n); } 回溯法有哪些信誉好的足球投注网站解空间 void NQueens(int n) { int k=1; x[1]=0; while(k0) { 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--; } } 实验结果及分析 n 皇后问题解的情况 皇后的个 问题的解 数 N=1 X=(1) N=2 无解 N=3 无解 N=4 X1=(2,4,1,3); X2=(3,1,4,2) N=5 X1=(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=7 40 个解 N=8 92 个解 4. 实验程序 随着 N 的增大，解的个数增多，以 N=4为例 #include stdio.h #includemath.h #define N 4 /* 定义棋盘大小 */ static int sum; /* 当前已找到解的个数 */ static int x[N]; int place(int k) { int j; for (j = 0; j k; j ++) if (x[j] == x[k] || abs(j - k) == abs(x[j] - x[k])) return 0; 2 / 6 return 1; } /* 打印棋局 */ void chessboard() { int i,j; int site[N]; printf( 第 %d种解法 :\n, ++ sum); for (i = 0; i N; i ++) { for (j = 0; j N; j ++) if (j == x[i]) {printf(Q );site[i]=j+1;} else printf(* ); printf(\n); } printf(A%d(,sum); for(i = 0; i