回溯法解决N后问题.doc

《回溯法解决N后问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计技巧与分析论文题目：回溯法解决N后问题实验报告院系：计算机与通信工程学院班级：计算机科学与技术08-1班姓名：***学号：****回溯法解决N后问题实验名称随机与回溯结合解决八皇后问题课程名称算法分析与设计姓名***专业班级学号计算机08-1班****日期2011.06.15地点西一楼207成绩教师***，***一、实验目的1.掌握回溯法的设计思想。2.设计回溯算法完成N后问题求解。3.考察回溯法求解问题的有效程度。二、实验要求1.输入皇后个数N。2.用回溯法解决N后问题的所有解，并表示出来。3.输出解决N后问题所需时间。三、实验内容（1）为解决这个问题，我们把棋盘的横坐标定为i，纵

2、坐标定为j,i和j的取值范围是从１到８。当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。（2）为第i个皇后选择位置的算法如下：for(j=1;j<=8;j++)/*第i个皇后在第j行*/if((i,j)位置为空)）/*即相应的三个数组的对应元素值为1*/{占用位置（i,j）/*置相应的三个数组对应的元素值为0*/ifi<8为i+1个皇后选择合适的位置；else输出一个解}一、实验结果皇后个数为1：皇后个数为2：皇后个数为3：皇后个数为4：皇后个数为8时：一、实验心得本实验是在别人代码的基础上，结合自己对回溯算法的理解改的。在最初的时候，遇到了很大

3、的麻烦，毕竟是改的别人的代码，对代码的理解不是很透彻，出现了很多错误，但在同学们的帮助下，通过自己的一个下午加一个晚上的修改，终于调试成功。在做实验的过程中，我不知道怎么获得系统时间，通过查阅资料和上网搜索，得到了答案：intiStart,iEnd;iStart=GetTickCount();//得到系统时间nQueen(n);iEnd=GetTickCount();//得到系统时间cout<<"Itneed"<

4、e#include#include#includeclassQueen{friendintnQueen(int);private:boolPlace(intk);voidBacktrack(intt);voidOutput();intn,//皇后个数*x;//当前解longsum;//当前已找到的可行性方案数};boolQueen::Place(intk){for(intj=1;j

5、

6、(x[j]==x[k])){returnfalse;}}

7、returntrue;}voidQueen::Backtrack(intt){if(t>n){sum++;Output();}else{for(inti=1;i<=n;i++){x[t]=i;if(Place(t)){Backtrack(t+1);}}}}intnQueen(intn){QueenX;X.n=n;X.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++){p[i]=0;}X.x=p;X.Backtrack(1);delete[]p;returnX.sum;}voidQueen::Output(){cout<<"*****第"<

8、"图解*****";cout<<"┌";//head行for(intk=1;kn-1){cout<<"└";//end行fo

9、r(k=1;k>n;intiStart,iEnd;iStart=GetTickCount();//得到系统时间nQueen(n);iEnd=GetTickCount();//得到系统时间cout<<"Itnee