//求解n皇後問題
#include <stdio.h>
#include <stdlib.h>
#define N 20 //最多皇後個數
int q[N]; //存放各皇後所在的列号,即(i,q[i])為一個皇後位置
int count=0; //累計解個數
void dispasolution(int n) //輸出n皇後問題的一個解
{
printf(" 第%d個解:",++count);
for (int i=1;i<=n;i++)
printf("(%d,%d) ",i,q[i]);
printf("\n");
}
bool place(int i,int j) //測試(i,j)位置能否擺放皇後
{
if (i==1) return true; //第一個皇後總是可以放置
int k=1;
while (k<i) //k=1~i-1是已放置了皇後的行
{ if ((q[k]==j) || (abs(q[k]-j)==abs(i-k)))
return false;
k++;
}
return true;
}
void queen(int i,int n) //放置1~i的皇後
{ if (i>n)
dispasolution(n); //所有皇後放置結束
else
{
for (int j=1;j<=n;j++) //在第i行上試探每一個列j
if (place(i,j)) //在第i行上找到一個合适位置(i,j)
{ q[i]=j;
queen(i+1,n);
}
}
}
void main()
{ int n; //n為存放實際皇後個數
printf(" 皇後問題(n<20) n=");
scanf("%d",&n);
if (n>20)
printf("n值太大,不能求解\n");
else
{ printf("%d皇後問題求解如下:\n",n);
queen(1,n); //放置1~i的皇後
}
}