#include <stdio.h>
#include <stdlib.h>
/****思路是，一行一行的填上皇后，每次只需要判断新加的皇后在列、两条对角线是否冲突****/
int qiPan[10][10];///全局变量，棋盘
int counter = 0;///全局变量，合法布局数目
void Trial(int i,int n);///进入此函数时，n*n的棋盘上前i-1行己经填好，而且合法。考虑C语言特色，子函数中是(n-1)
void showQiPan(int n);
int isValid(int i,int j,int n);///正在尝试的皇后的行列数，1代表合法
int main()
{
printf("N皇后问题，同行同列同对角线只能出现一个皇后，本程序输出所有合法布局及其个数\n");
printf("棋盘上位置是0代表没有放皇后，1代表放了皇后\n");
int n =4;
while(n!=0)
{
printf("你想研究几皇后问题，必须小于11的正整数，输入0代表结束程序：\n");
scanf("%d",&n);
///初始化棋盘
if(n==0)
break;
int i,j;
for(i=0;i<n;++i){
for(j=0;j<n;++j)
qiPan[i][j] = 0;
}
///开始放皇后
Trial(0,n);
printf("一共%d个合法布局\n",counter);
counter = 0;
}
return 0;
}
void Trial(int i,int n){
if(i>n-1){
///输出合法布局..........................................
showQiPan(n);
printf("下一个合法布局：\n");
counter = counter +1;
}
else{
int j;///j代表列，在i行j列试图放皇后
for(j = 0; j < n; ++j){
///放皇后.............................................
qiPan[i][j] = 1;
///若合法布局，则开始下一行，递归；否则移走这个皇后
if(isValid(i,j,n)==1){
Trial(i+1,n);
}
///else{
///移走当前皇后...................................
qiPan[i][j] = 0;
///}
}
}
}
void showQiPan(int n){
int i,j;
for(i=0;i<n;++i){
for(j=0;j<n;++j){
printf("%d ",qiPan[i][j]);
}
printf("\n");
}
}
int isValid(int i,int j,int n){
///行肯定没问题，每次都是新的一行
//printf("%d行开始试图下棋\n",i+1);
int temp;
if(i==0)
return 1;
else{
///看前i-1行的所有j列是否有皇后
for(temp = 0; temp < i; ++temp){
if(qiPan[temp][j]==1){
//printf("列冲突了，第%d行第%d列是1导致的\n",temp+1,j+1);
return 0;
}
}
///看“主对角线”
int a,b;
for(a = i-1,b = j-1; a>=0&&b>=0;a--,b--)
if(qiPan[a][b]==1){
//printf("主对角线冲突了，第%d行第%d列是1导致的\n",a+1,b+1);
return 0;
}
///看“副对角线”
for(a = i-1,b = j+1; a>=0&&b<=n-1;a--,b++)
if(qiPan[a][b]==1){
//printf("副对角线冲突了，第%d行第%d列是1导致的\n",a+1,b+1);
return 0;
}
return 1;
}
}
