N皇后问题的拉斯维加斯算法和回溯算法

#include<iostream> #include<cstdlib> #include<ctime> #define N 20 using namespace std; int T[100]; //(i,T[i])指放在第i行第T[i]列 int k=0; //当前已经放置了多少行 bool place(int j); bool backtrace(int row){ //当前已经放置完第1,2,3...row行，从第row+1行开始回溯 T[k+1]=0; if(row==N) return true; while(k>=row){ T[k+1]+=1; while((k+1)<=N&&place(T[k+1])==false) //没法放置在该位置 T[k+1]++; if(T[k+1]<=N){ if((k+1)==N) return true; else { k++; T[k+1]=0; } } else { k--; } } return false; } bool place(int j){ //检查(k+1,j)是否能放入皇后 for(int i=1;i<=k;i++) if((j-T[i])==0||abs(j-T[i])==k+1-i) return false; return true; } bool QueensLv(int stepVegas){ k=0; int nb; int col; while(true){ nb=0; for(int j=1;j<=N;j++){ if(place(j)){ nb++; if((rand()%nb+1)==1) col=j; } } if(nb>0){ k++; T[k]=col; } if(nb==0||k==stepVegas) break; } //1,2,3...k行已经放置完毕 if(nb>0){ return backtrace(stepVegas); } else { return false; } } void print(){ for(int i=1;i<=N;i++) cout<<"("<<i<<","<<T[i]<<")"<<endl; return; } void test(int m){ double time[N+1]={0.0}; int correct[N+1]={0}; clock_t start,ends; bool success; for(int i=1;i<=N;i++){ int count=0; while(true){ start=clock(); success=QueensLv(i); ends=clock(); time[i]+=(ends-start); count++; if(success) { correct[i]++; } if(count==m){ break; } } } int count=0; while(1){ k=0; start=clock(); success=backtrace(0); ends=clock(); time[0]+=(ends - start); count++; if(success){ correct[0]++; } if(count==m){ break; } } for(int i=0;i<=N;i++){ double t=time[i]/CLOCKS_PER_SEC; cout<<"stepVegas="<<i<<",success:"<<correct[i]<<","<<"total time is "<<t<<",average success time is "<<t/correct[i]<<endl; } return; } int main(){ srand(time(0)); cout<<"input m:"; int m; cin>>m; cout<<"N="<<N<<endl; test(m); return 0; }

可以看到，最优stepVegas在N/2左右。