问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0
咱们首先要解决的是n皇后问题，就例如这里就放黑皇后这一种
假设棋盘是4*4:
首先我们要求的是求解出其中的一种情况，我们借助一个软件来分析一下
到这里我们发现第上面第三步的时候，第三个皇后放在第三行的任意位置都不成立，这个时候我们就要回溯到底二个皇后改变位置
我们发现此时第四个皇后也没有位置可放，于是我们回溯到底三个皇后，发现此时第三个皇后也没位置可放，我们就回溯到第二个皇后，发现第二个皇后也不行，此时我们就回溯到底一个皇后，改变位置
此时我们就求出了其中的一个解。
我们来看代码（这是教材上的一个代码，是用回溯法求出一个解）
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXSIZE 100
int x[MAXSIZE];//x[k]代表的第k个皇后在x[k]列，k从0开始，列也从0开始
int place(int k);//判断是否满足条件的函数
void queeen(int n);
int main(void)
{
queeen(4);
return0;
}
void queeen(int n)
{
memset(x,-1,n);//先初始化x数组，前n个数为 -1
int k =0;//k代表的是皇后的序号（我这里是从0开始的），也代表的是数组的第几行
while(k >=0)
{
x[k]++;
while(x[k]< n && place(k)==1)
x[k]++;
if(x[k]< n && k == n -1)
{
for(int i =0; i < n; i++)
printf("%d\n",x[i]+1);
return;
}
if(x[k]< n && k < n-1)
k = k +1;
else
x[k--]=-1;//回溯到上一个皇后 位置置为-1
}
printf("无解\n");
}
int place(int k)
{
for(int i =0; i < k; i++)
{
if(x[i]== x[k]|| fabs(i - k)== fabs(x[i]- x[k]))//要注意的是这里利用了斜率的绝对值是否为1来确定是否在一个斜线上。
return1;
}
return0;
}
}
上面这是利用回溯法求解出一个解，下面我们用递归来求解出解的个数
递归求解重要的就是找出递归结束的条件，这里有两个限制条件。一个是当所有的皇后都放置好且正确后要跳出递归，还有一个就是不能满足题目的条件是不能进入下一个递归的。
代码如下
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXSIZE 100
int x[MAXSIZE];//x[k]代表的第k个皇后在x[k]列，k从0开始，列也从0开始
int count =0;
int n =8;
void queen(int k);
int main(void)
{
queen(0);
printf("%d\n",count);
return0;
}
void queen(int k)
{
for(int i =0; i < k -1; i++)//判断是否进入下一个递归的条件
{
int judge = x[i]- x[k -1];
if(judge ==0|| fabs(k -1- i)== fabs(judge))
return;
}
if(k == n)//跳出递归的条件
{
count++;
return;
}
for(int j =0; j < n; j++)
{
x[k]= j;
queen(k +1);
}
}
接下来就是2n皇后问题，用递归解决，其实就是等白皇后放好之后，黑皇后在放
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXSIZE 1000
int bqueen[MAXSIZE];//黑皇后
int wqueen[MAXSIZE];//白皇后
int chessboard[MAXSIZE][MAXSIZE];//1:能放 0:不能放
int count =0;
int n;
int place(int k);
int BlackQueen(int k)
{
int i;
int j;
for(i =0; i < k -1; i++)
{
int judge = bqueen[i]- bqueen[k -1];
if(judge ==0|| fabs(k -1- i)== fabs(judge))
return0;
}
if(k == n)
{
count++;
return0;
}
for( j =0; j < n; j++)
{
if(j != wqueen[k]&& chessboard[k][j])
{
bqueen[k]= j;
BlackQueen(k +1);
}
}
}
int WhiteQueen(int k)
{
int i;
int j;
for( i =0; i < k -1; i++)
{
int judge = wqueen[i]- wqueen[k -1];
if(judge ==0|| fabs(k -1- i)== fabs(judge))
return0;
}
if(k == n)
{
BlackQueen(0);
return0;
}
for( j =0; j < n; j++)
{
if(chessboard[k][j])
{
wqueen[k]= j;
WhiteQueen(k +1);
}
}
}
int main(void)
{ int i;
int j;
// freopen("input3.txt","r",stdin);//这是我直接从文件中读取数据
scanf("%d",&n);
for(i =0; i < n; i++)
for(j =0; j < n; j++)
scanf("%d",&chessboard[i][j]);
WhiteQueen(0);
printf("%d\n",count);
return0;
}
下面 我上传一下蓝桥杯的5组测试数据
input 1
3
1 1 0
1 1 1
1 1 0
output1
0
input2
4
1 1 1 1
1 0 1 1
1 1 1 1
1 1 1 1
output2
2
input 3
5
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
output3
12
input4
6
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
output4
12
input5
7
1 1 1 1 1 1 0
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
output5
408