#include<stdio.h>
#include<math.h>
#include<conio.h>
const int Queens=8;
int Site[Queens]; //此数组用来存放每一个皇后的位置
int iCount=0;
void Queen(int n);
void Output();
int IsValid(int n); //判断第n个皇后放上去后是否与前面的皇后有冲突
void main()
{
printf(" 八皇后的解法:\n");
printf("----------------------------------------\n");
Queen(0);
getch();
}
void Queen(int n)
{
if(n==Queens) //n从0开始,等于8时输出一个解并回溯
{
Output();
return;
}
for(int i=1;i<=Queens;i++) //i表示第n个皇后可能所在的列位置
{
Site[n]=i;
if(IsValid(n))
Queen(n+1);
}
}
void Output()
{
int i;
iCount++;
printf("No.%-5d",iCount);
for(i=0;i<Queens;i++)
printf("%d ",Site[i]);
printf("\n");
}
int IsValid(int n)
{
for(int i=0;i<n;i++)
{
if(Site[i]==Site[n]) //表示在同一列
return 0;
if(abs(Site[i]-Site[n])==n-i) //表示在对角线上
return 0;
}
return 1; //表示没有冲突
}