新皇后问题(3种)

数组和递归解决皇后问题：

#include #include # define OK 1 #define ERROR 0 using namespace std; #include #include

#define CLOCK_PER_SEC 1000

const int N=20; //最多放皇后的个数 int q[N]; //各皇后所在的行号 int m= 0; //统计解得个数 //输出一个解 void print(int n) {

int i,j; m++;

cout<<\"第\"<cout<<\"(\"<for(i=1;i<=n;i++) //行 {

for(j=1;j<=n;j++) //列 {

if(q[i]!=j)

cout<<\"x \"; else

cout<<\"Q \"; }

cout<//检验第i行的k列上是否可以摆放皇后 int find(int i,int k) {

int j=1;

while(j//第j行的皇后是否在k列或(j,q[j])与(i,k)是否在斜线上 if(q[j]==k || abs(j-i)==abs(q[j]-k)) return 0; j++; }

return 1; }

//放置皇后到棋盘上 void place(int k,int n) {

int j; if(k>n)

print(n); else {

for(j=1;j<=n;j++) //试探第k行的每一个列 {

if(find(k,j)) {

q[k] = j;

place(k+1,n); //递归总是在成功完成了上次的任务的时候才做下一个任务 } } }

}

int main(void) {

clock_t start,finish; double totaltime; start=clock();

for(int i=0;i<10000000;i++) { int n;

cout<<\"请输入皇后的个数(n<=20),n=:\"<>n; if(n>20)

cout<<\"n值太大，不能求解!\"<cout<<\"n皇后问题求解如下(每列的皇后所在的行数):\"<break; }

finish=clock();

totaltime=(double)(finish-start)/CLOCK_PER_SEC;

cout<<\"程序运行所用时间为:\"<return 0; }

用类和递归解决皇后问题： #include

#define CLOCK_PER_SEC 1000

#include #include using namespace std; #define N 100 class Queen {

public:

Queen(){num=-1;}

void Print(int n);//输出皇后的排列，打出的数字为每个皇后的坐标 int Check(int i,int k);//判断位置是否符合要求 void Queens(int k,int n);//递归调用 int count();//计数 private: int q[N]; int num; };

void main() {

clock_t start,finish; double totaltime; start=clock();

for(int i=0;i<10000000;i++) {

Queen Q; int n;

cout<<\"请输入Queen的数目(n>0):\"<>n; if(n>0) {

cout<<\"Queen可能的位置坐标:\"<cout<<\"共有 \"<cout<<\"ERROR输入数字错误\"<finish=clock();

totaltime=(double)(finish-start)/CLOCK_PER_SEC; cout<<\"runtime is:\"<void Queen::Queens(int k,int n)//计算出皇后的排列，k是当前皇后数量，n是数量上限 { int i;

if(k>n)//如果达到里要求的数量输出皇后排列 { Print(n); count(); }

else //否则在适当的位置添加一个新皇后 {

for(i=1;i<=n;i++)

if(Check(i,k)) //判断该行中该位置放置'皇后'是否符合要求

{

q[k]=i; //记录改行中该点的位置 Queens(k+1,n); //放置下一行的'皇后' } } }

void Queen::Print(int n) {

int i;

for(i=1;i<=n;i++)

cout<<\"(\"<int Queen::Check(int i,int k) {

int j; j=1;

while(jif((q[j]==i) || abs(q[j]-i)==abs(j-k)) //判断列，判断斜线 return 0; //不符合返回0 j++; }

return 1; //符合返回 }

int Queen::count() {

num++; return num; }

利用栈存储和递归实现的解决皇后问题： # include # include #include

#define CLOCK_PER_SEC 1000 # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 #define ERROR 0 using namespace std; typedef int Status;

typedef struct SElemType{ int a;int b;int c; }SElemType; typedef struct{

SElemType *base; SElemType *top;

int stacksize; }SqStack;

Status InitStack(SqStack &S){

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base;

S.stacksize=STACK_INIT_SIZE; return OK; }//InitStak

Status GetTop(SqStack S,SElemType &e, int &i){ if(S.top==S.base) return ERROR; e=*(S.top-i); return OK; }//GetToop

Status Push(SqStack &S,SElemType e){ if (S.top-S.base>=S.stacksize){

S.base=(SElemType*)realloc(S.base,(S.stacksize STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize;

S.stacksize += STACKINCREMENT; }//if

*S.top++=e; return OK; }//PUSH

Status Pop(SqStack &S,SElemType &e){ if(S.top==S.base)return ERROR; e = * --S.top; return OK; }//Pop

int find_check(int k,int i,SqStack &S, SElemType &e){ int j;

for(j=1;j+ GetTop( S,e,j);

if(e.c==i||e.b-k==e.c-i||e.b-k==i-e.c)

return 0; //当m行与n行皇后位于同一对角线时，不符合要求，返回0 }

return 1;}

void Queen(int k, int n,SqStack &S, SElemType &e,int &numb){//计算出皇后的排列，i是当前皇后数量，n是数量上限 int i,j,l,x; if(k>n)

{//如果达到里要求的数量输出皇后排列 numb++;

for(l=n;l>0;l--) {

for(x=1;x<=n;x++) {

GetTop( S, e,l); if(x==e.c)

cout<<\"Q \"; else cout<<\"x \"; } cout<for(j=n; j>0; j--) {

GetTop( S, e,j);

cout<<\"(\"<cout<cout<<'\\n'<Pop(S,e); } else

{//否则在适当的位置添加一个新皇后 for(i=1; i<=n; i++) {

if(find_check(k,i,S,e)) {

e.b=k;e.c=i; Push(S,e);

Queen(k+1, n,S,e,numb); if(i==n)

Pop(S,e);

} else{

if(i==n)

Pop(S,e);} } } }

int main() {

clock_t start,finish; double totaltime; start=clock();

for(int i=0;i<10000000;i++) {

int n,numb=0;SqStack S;SElemType e; InitStack(S);

cout<<\"请输入皇后的个数n为:\"<>n;

e.a=n;e.b=1;e.c=1; Queen(1,n,S,e,numb);

cout<<\"共有 \"<break;} finish=clock();

totaltime=(double)(finish-start)/CLOCK_PER_SEC;

cout<<\"程序运行所用时间为:\"<计算时间的模板: #include

#define CLOCK_PER_SEC 1000

clock_t start,finish;

double totaltime;

start=clock();

for(int i=0;i<10000000;i++) { }

finish=clock();

totaltime=(double)(finish-start)/CLOCK_PER_SEC;

cout<<\"程序运行所用时间为:\"<