随机与回溯结合解决N后问题实验报告.doc

算法分析与设计实验报告实验名称： 随机与回溯结合解决N后问题 课程名称： 算法分析与设计 姓名： 李少卿 专业班级： 计算机科学与技术08-1班 学号： 200807010119 日期： 2011.06.01 地点： 西一楼207 成绩： 地点： 苏晓珂、李灿林 1.实验目的结合随机算法和回溯求解N皇后问题，使得在NxN格的国际象棋上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。2.实验内容(1) 算法分析N皇后问题一般是采用回溯法求解，但当N值较大时，回溯算法效率较低，所以此次作业中将随机算法和回溯法结合起来求解N皇后问题，以提高算法的效率。引入随机算法，能保证每次找出的解是正确的，但可能在一次求解过程中找不出可行解，这一点在程序运行过程中能得到体现。所以解决N皇后问题所采取的方法是先用随机函数产生一部分的解（这一部分可以占全部的三分之一），再用回溯法将其余的结果计算出来。(2) 源代码#include #include #include using namespace std;int count,rand_count;/判断第k个皇后的位置是否满足要求bool place(int x,int k) int i; for (i = 1;ik;+i) if ( (xi=xk)|( abs(xi-xk)=abs(i-k) ) ) return false; return true;/回溯法+随机法求解n皇后问题void Rand_Back_n_queens(int n,int x) int k,mid; mid = n/3; time_t t; srand(unsigned) time(&t);printf(n随机产生的值：n); for (k = 1;kmid) +xk; while ( (xk=n)&(!place(x,k) ) +xk; if (xk=n) if (k=n) break; else +k; xk = 0; else xk = 0; -k; printf(n回溯法产生的值：n); for (int i = mid+1; i=n; +i) printf(%dt,xi);int main() int n; printf(回溯法+随机法求解n皇后问题，请输入n值(输入0则退出): ); while (scanf(%d,&n),0!=n) int *x = new intn+1; Rand_Back_n_queens(n,x); delete x; x = NULL; printf(nn请输入n值(输入0则退出): ); return 0;(3) 实验结果输入代码后编译并调试程序。当N等于8、9、10的时候分别可以得到以下的结果：3.总结与回顾在这次试验的代码设计中使用了随机函数来求得三分之一的解。首先要解决的问题就是随机函数的问题。随机函数是一个获得随机数很方便的工具，但是由于该函数的局限性，它每次重新开始运行时所产生的随机数都是相同的，就是获得了相同的数据，从而失去了它的随机性。所以随机函数就便成了伪随机函数。为了解决这个问题，我使用了时间函数来作为随机种子。从而使得每次获得的数据都因为时间的不同而不同。其次就是随机函数所产生的数据不一定是正确的解，所以每次产生随机数之后还要判断一下，不符合题目要求的要删掉，并重新执行随机函数直到产生正确的解。然后就是用之前所学到的回溯法来求得余下的解了。求解过程和单独用回溯法一样，不过因为上面产生随机解的