n皇后问题实验报告.doc

算法分析与设计报告N皇后问题N后问题算法一、实验目的及要求所要涉及或掌握的知识：1. 了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。2. 运用迭代的方法实现6皇后问题，求解得到皇后不相互攻击的一个解3. 在运用迭代的方法实现编程时，要注意回溯点二、问题描述及实验内容对6皇后问题求解，用数组c16来存皇后的位置。ci=j表示第i个皇后放在第j列。最后程序运行的结果是c16=1,5,8,6,3,7 三、问题分析和算法描述6-QUEENS的算法表示：输入：空。输出：对应于6皇后问题的解的向量c16=1,5,8,6,3,71. for k=1 to 62. ck=0 /没有放皇后3. end for4. flag=false5. k=16. while k=17. while ck=58. ck=ck+19. if c为合法着色 then set flag=ture 且从两个while循环退出10. else if c是部分解 then k=k+111. end while12. ck=0 /回溯并ck=013. k=k-114. end while15. if flag then output c16. else output “no solution”四、具体实现# include #include #include #include #include iostream using namespace std;int total = 0; /方案计数 void backtrace(int queen,int N) int i, j, k; cout为皇后放置位置n;for (i=1;) /首先安放第1行 if(queeniN) /皇后还可调整 k=0; /检查与第k个皇后是否互相攻击 while(ki&abs(queenk-queeni)&(abs(queenk-queeni)-abs(k-i) k+; if (k=i-1) /与第k个皇后互相攻击 queeni+; /第i个皇后右移一列，重测 continue; i+; /无冲突，安置下一行皇后 if(iN) continue; cout第total+1种为：n; for(int i=0;iN;i+) for(int j=0;jqueeni;j+) cout; cout; for(int k=queeni+1;kN;k+) cout; coutendl; total+; /方案数加1 if(total%5=0) coutendl; queenN-1+; / 将第8个皇后右移一列，前8个不动 i=N-1; /此处是制造机会，如不成功则回溯，关键一步 else /当前行皇后无法安置，回溯 queeni=0; /当前行皇后回归1列 i-; /回溯到前一行皇后 if(i0) /回溯到数组1行之前，结束 coutn针对 N 皇后问题，一共找到 total 种放置方法。 endl; coutendl; return; else queeni+; /前一行皇后右移一列 void main() while(1) clock_t start, finish; double duration; int N; cout请输入皇后个数：N; int* queen=new intN; for (int i=0;iN;i+) queeni = 0; /八皇后全放在第0列 int n=N; /* 定义数组pN用来存放结果序列，n为行号 */ start=clock(); total=0; backtrace(queen,N); finish=clock(); duration=(d