VC++八皇后问题新解

#include<stdio.h> #include<iostream.h> #include<time.h> int main() { clock_t start_time,end_time; int i,k,n=0,N,flag,not_finish=1,count=0; int *a; cout << "请输入N皇后问题规模："; cin >> N; a=new int[N+1]; i=1; /*正在处理的元素下标，表示前i-1个元素已符合要求，正在处理第i个元素*/ a[1]=1; /*为数组的第一个元素赋初值*/ start_time=clock(); while(not_finish) /*not_finish=1:处理尚未结束*/ { while(not_finish && i<=N) /*处理尚未结束且还没处理到第N个元素*/ { for(flag=1,k=1; flag && k<i; k++) /*判断是否有多个皇后在同一行*/ { if(a[k]==a[i]) flag=0; } for(k=1; flag && k<i; k++) /*判断是否有多个皇后在同一对角线*/ { if((a[i] == a[k]-(i-k)) || (a[i]==a[k]+(i-k))) flag=0; } if(!flag) /*若存在矛盾不满足要求，需要重新设置第i个元素(即第i列的皇后)*/ { if(a[i] == a[i-1]) /*若a[i]的值已经经过一圈追上a[i-1]的值*/ { i--; /*退回一步，重新试探处理前一个元素(即前一列的皇后位置)*/ if(i>1 && a[i]==N) a[i]=1; /*当a[i]为N时将a[i]的值置1*/ else if(i==1 && a[i]==N) not_finish=0; /*当第一位的值达到N时结束,因为此时回朔已经到头*/ else a[i]++; /*将a[i]的值取下一个值*/ } else if(a[i]==N) a[i]=1; else a[i]++; /*将a[i]的值取下一个值*/ } else //否则开始设置第i+1个元素(即第i+1列的皇后) if(++i<=N) if(a[i-1]==N) a[i]=1; /*若前一个元素的值为N则a[i]=1*/ else a[i]=a[i-1]+1; /*否则元素的值为前一个元素的下一个值*/ } if(not_finish) { n++; /*++count; printf((count-1)%3? "[%2d]: " : "\n[%2d]: ",count); for(k=1;k<=N;k++) //输出结果 {printf("%d ",a[k]);}*/ if(a[N-1]<N) a[N-1]++; //修改倒数第二位的值 else a[N-1]=1; i=N-1; //开始寻找下一个满足条件的解 } } cout <<endl <<N <<" 皇后问题" <<"一共有 "<< n <<" 种情况" << endl; end_time=clock(); cout <<endl <<"共耗费时间：" <<end_time-start_time <<"毫秒" << endl; char ch; cin >>ch; return 0; }