八皇后问题回溯,概率算法及回溯+概率可执行代码

《八皇后问题回溯,概率算法及回溯+概率可执行代码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#include"math.h"#include"randomnumber.h"usingnamespacestd;classQueen{friendvoidnQueenlv(int);friendvoidnQueenrc(int);friendvoidnQueen_lv_rc(int,int);friendintnQueen_sum(int,int);private:boolPlace(intk);//测试皇后k置于第x[k]列的合法性boolQueensLV(void);//随机放置n个皇后拉斯维加斯算法voidBa

2、cktrack(int);//回溯函数intn,stopVegas;//皇后个数int*x,y[1000];//解向量intstep;//统计步数};boolQueen::Place(intk)//Place(k)用于测试将皇后k置于第x[k]列的合法性{for(intj=1;j

3、

4、(x[j]==x[k]))//合法性测试表达式returnfalse;returntrue;}boolQueen::QueensLV(void)//QueensLV(void)实现在棋盘上随机放置n个皇后拉

5、斯维加斯算法{RandomNumberrnd;//随机数产生器intk=1;//下一个放置的皇后编号intcount=1;while((k<=stopVegas)&&(count>0)){count=0;for(inti=1;i<=n;i++){x[k]=i;if(Place(k)){y[count++]=i;}}if(count>0){x[k++]=y[rnd.Random(count)];//随机位置step++;}}return(count>0);//count>0表示放置成功}voidQueen::Backtrack(intt){if(t<=n){

6、for(inti=1;i<=n&&x[0]!=1;i++){x[t]=i;if(Place(t)){++step;if(t==n){x[0]=1;}//printf("%d/%d",t,x[t]);Backtrack(t+1);}}}}voidnQueenlv(intn)//解n后问题的拉斯维加斯算法{QueenX;//初始化X.n=n;X.step=1;X.stopVegas=n;int*p=newint[n+1];for(inti=0;i<=n;i++)p[i]=0;X.x=p;//反复调用随机放置n个皇后拉斯维加斯算法，直至放置成功while(!X.

7、QueensLV());cout<<"经过"<

8、++){for(intj=1;j<=n;j++){if(j==p[i])cout<<"Q"<<"";elsecout<<"*"<<"";}cout<

9、());Z.Backtrack(Z.stopVegas+1);}for(i=1;i<=n;i++){for(intj=1;j<=n;j++){if(j==p[i])cout<<"Q"<<"";elsecout<<"*"<<"";}cout<

10、]=0;}S.x=p;while(p[0]!=1){while(!