|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 wd/ 于 2020-3-29 21:09 编辑
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef struct
{ int c[MaxSize]; //c[i]存放第i个皇后的列号
int top; //栈顶指针
} StackType; //声明顺序栈类型
StackType St; //定义栈st
void dispasolution() //输出一个解
{static int count=0;
printf(" 第%d个解:",++count);
for(int i=1;i<=St.top;i++)
printf("(%2d,%2d)",i,St.c[i]);
printf("\n");
}
bool place(int k) //测试(k,j)是否与1~k-1的皇后有冲突
{ if (k==1) return true;
for(int i=1;i<k;i++) //放第一个皇后时没有冲突
if(St.c[i]==St.c[k]||(St.c[k]-St.c[i])==(k-i)||(St.c[k]-St.c[i])==(i-k))
return false;
return true; //没有冲突时返回真
}
void queen(int n) //求解n皇后问题
{ St.top=0; //初始化栈顶指针,为了让皇后从第1行开始,不用下标0
St.c[++St.top]=0; //进栈。c[1]=0,表示从第1个皇后开始,初始列号为0,因为后面要++
while (St.top>0) //栈不空时循环
{
for(++St.c[St.top];St.c[St.top]<=n;St.c[St.top]++)
if(place(St.top)) break;
if(place(St.top))
{
if(St.top==n)
{
dispasolution();
St.c[St.top--]=0;
}
else{St.top++;}
}
else{St.c[St.top--]=0;}
}
}
int main()
{ int n; //n存放实际皇后个数
printf("皇后问题(n<20) n=");
scanf("%d",&n);
if (n>20) printf("n值太大\n");
else
{ printf(" %d皇后问题求解如下:\n",n);
queen(n);
system("pause");
}
return 1;
} |
|