n皇后问题实验报告.doc

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

1、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的算法表示：输入：空。输出：对应于6皇后问题的解的向量c[1…6]={1,5,8,6,3,7}1.

2、      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.      endwhile12.   c[k]=0              //回溯并c[k

3、]=013.   k=k-114.   endwhile15.   ifflag thenoutputc16.   elseoutput“nosolution”四、具体实现#include#include#include#include#include"iostream"usingnamespacestd;inttotal=0;//方案计数voidbacktrace(intqueen[],intN){inti,j,k;cout<<"★为皇后放置位置";for(i=1;;){//首先安放第1行  if(queen[i

4、]

5、       for(intj=0;j

6、归1列   i--;//回溯到前一行皇后   if(i<0)   {//回溯到数组1行之前，结束    cout<<"针对"<>N;  int*queen=newint[N];  f

7、or(inti=0;i