首页 > 代码库 > 8皇后

8皇后

#include <stdio.h>
#include <math.h>
#include <time.h>
#define max 1000
int sum=0;
bool place (int k,int x[])
{

for (int j=1;j<k;j++)
if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;
return true;

void backtrack (int t,int x[],int n)
{


int i,j;

if (t>n){ 
sum++;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==x[j])printf("Q ");
else printf("# ");}
printf("\n");}
printf("\n\n");
/*for(i=1;i<=n;i++)
printf("%d",x[i]);
*/

}
else
for (i=1;i<=n;i++) {
x[t]=i;
if (place(t,x)) backtrack(t+1,x,n);
}

}
void main()
{
int x[max],num;
clock_t start_time,end_time;
printf("按任意键继续,Q键结束。");
char ch=getchar();
while(ch!=‘q‘)
{ sum=0;//初始化sum,避免sum累加
printf("请输入皇后的个数为:\n");
scanf("%d",&num);
if(num==2||num==3)printf("输入错误,无解!\n");
else
{
printf("输出皇后排列结果为:\n");
start_time=clock();
backtrack(1,x,num);
end_time=clock();
printf("一共有%d种排列方法。输出耗时:%dms。\n",sum,end_time-start_time);
}

printf("按Q键结束。\n");
ch;
}

}

8皇后