题目描述
给定一个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
原题链接：[蓝桥杯][基础练习VIP]2n皇后问题
在我们学习2n皇后问题前，需要了解回溯法的一个经典题型：八皇后问题
一、首先贴上八皇后问题：
给定一个8*8的棋盘。现在要向棋盘中放入8个皇后使任意的两个皇后都不在同一行、同一列或同一条对角线上问总共有多少种放法？
我们需要明确：
- 1、会有八个皇后被放入
- 2、每一行放一个（也仅有一个）
- 3、每一列也会有一个（也仅有一个）
- 4、如果用全排列或者八个for循环，结果多半是惨烈的
关键代码：
int vis[10]; //vis[i]=1 表示第i【列】被访问过了，后面此列不被访问
int a[10]; //a[i]=j 表示第i个皇后（第i行）的位置为j->a[j]
void dfs(int step,int n) { //安排第step个皇后（即第step【行】）if(step==n+1) { //递归边界，表示n个皇后已经安排好了cnt++;} else {for(int i=1; i<=n; i++) { //遍历i列if(vis[i]==0) { //第i列必须是之前没访问过得一列bool tag = true;for(int j=1; j<step; j++) { //遍历a数组1~step:查找与之前已经定好位的皇后是否冲突if(step-j == i-a[j] || step-j == a[j]-i) {//当前位置：（step,i） 之前位置（j,a[j]），若他们在对角线上，则斜率（step-j)/(i-a[j])为1或-1tag = false;break;}}if(tag) { // i列符合条件vis[i]=1; // 访问a[step] = i;dfs(step+1,n);// 安排下一个皇后vis[i]=0; // 回溯：恢复DFS之前的状态}}}}
}近似思路题型应用变形，可见 棋盘多项式-题解(C/C++描述)-详细解释
二、迁移到2n皇后中问题：
不同之处为：每一行除了有一个黑皇后外，还会有一个白皇后。
所以我们按照上述做法查找一个位置给黑皇后之后，还需要在查找一次，给白皇后定位，只有两位皇后都安排完毕了，才能进入下一行的定位。
所以你会发现，不管是vis数组，还是皇后位置的数组，我们都需要准备两份
下面提供完整代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int cnt = 0;
int map[10][10]; //存储地图
int visb[10]; //visb[i]=1第i列已经有了黑皇后
int visw[10]; //白皇后，同上
int black[10]; //black[i]=j 表示第i个黑皇后（i行）在第j列
int white[10]; //白皇后的位置，同上
void dfs(int step,int n) { //step代表第几行，要安排第几个皇后if(step==n+1) {cnt++;} else {for(int i=1; i<=n; i++) { //第step行遍历i列（i->1-n）bool black_tag = true;if(visb[i]==0 && map[step][i]==1) {for(int j=1; j<step; j++) { //跟之前已经定好位的皇后做比较if(step-j == i-black[j] || step-j == black[j]-i) { //斜对角方向 （step,i）和（j,a[j]）的斜率为1或-1black_tag = false;break;}}if(black_tag) {visb[i]=1; //这一列有皇后了，后面一整列都不能访问black[step] = i; //(step,i)->(step,a[step])for(int k=1; k<=n; k++) {if(k==i) continue;bool white_tag = true;if(visw[k]==0 && map[step][k]==1) {for(int j=1; j<step; j++) { //跟之前已经定好位的皇后做比较if(step-j == k-white[j] || step-j == white[j]-k) { //斜对角方向 （step,k）和（j,a[j]）的斜率为1或-1white_tag = false;break;}}if(white_tag) {visw[k]=1;white[step] = k;dfs(step+1,n); //搜索下一行（下一个皇后）visw[k]=0;}}}visb[i]=0;}}}}
}
int main() {int n;cin>>n;for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {cin>>map[i][j];}}dfs(1,n);cout<<cnt;return 0;
}