n皇后问题实验报告.doc

《n皇后问题实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计报告 N皇后问题N后问题算法一、实验目的及要求所要涉及或掌握的知识：1.      了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。2.      运用迭代的方法实现6皇后问题，求解得到皇后不相互攻击的一个解3.      在运用迭代的方法实现编程时，要注意回溯点二、问题描述及实验内容对6皇后问题求解，用数组c[1…6]来存皇后的位置。c[i]=j表示第i个皇后放在第j列。最后程序运行的结果是c[1…6]={1,5,8,6,3,7}三、问题分析和算法描述6-QUEENS的算法表示：输入：空。输出：对应于

2、6皇后问题的解的向量c[1…6]={1,5,8,6,3,7}1.      fork=1to62.      c[k]=0         //没有放皇后3.      endfor4.      flag=false5.      k=16.      whilek>=17.         whilec[k]<=58.               c[k]=c[k]+19.               ifc为合法着色 thensetflag=ture且从两个while循环退出10.            elseifc是部分解thenk=k+111

3、.      endwhile12.   c[k]=0              //回溯并c[k]=013.   k=k-114.   endwhile15.   ifflag thenoutputc16.   elseoutput“nosolution”四、具体实现#include#include#include#include#include"iostream"usingnamespacestd;inttotal=0;//方案计数voidbacktrace(intqueen[],

4、intN){inti,j,k;cout<<"★为皇后放置位置";for(i=1;;){//首先安放第1行  if(queen[i]

5、(i

6、++;//将第8个皇后右移一列，前8个不动   i=N-1;//此处是制造机会，如不成功则回溯，关键一步  }  else//当前行皇后无法安置，回溯  {   queen[i]=0;//当前行皇后回归1列   i--;//回溯到前一行皇后   if(i<0)   {//回溯到数组1行之前，结束    cout<<"针对"<

7、(){while(1){  clock_tstart,finish;  doubleduration;  intN;  cout<<"请输入皇后个数："<>N;  int*queen=newint[N];  for(inti=0;i

8、h-start);    cout<<"为找出放置方法系统共耗时"<