有了上次的八皇后的基础。这次准备解决2n皇后的问题，：
//问题描述
// 给定一个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
先补充贴上八皇后第二种方法的代码：
感谢
@ Almost_Lover
对代码的优化和注释，比之前更容易理解了
//参考程序二
#include <stdio.h>
int record[][]; // record记录全部解，共92种情况，每种情况都是长度为8的数串
int mark[]; // mark记录当前解，即当前8皇后在棋盘上的情况
int count = ; // 计数器，共92种
bool columnIsOk[], degree45IsOk[], degree135IsOk[]; // 分别记录列方向(上下方向)，45度，135度方向上被控制的情况
void tryToPut(int row); // 声明递归函数，逐行尝试放置皇后，递归求得92种情况 int main() {
// 初始化棋盘，上下方向，45度方向，135度方向都未被控制
for(int i = ; i <=; i++)
columnIsOk[i] = true;
for(int i = ; i < ; i ++)
degree45IsOk[i] = degree135IsOk[i] = true; // 递归求解，获得全部可能情况
tryToPut(); int getResultNums; // 想要获得几种情况
int oneOfResults; // 总共92种情况中具体一种
scanf("%d", &getResultNums); // 按照输入，取出来结果
while(getResultNums --) {
scanf("%d", &oneOfResults);
for(int i = ; i <=; i++)
printf("%d", record[oneOfResults - ][i]);
printf("\n");
} return ;
} void tryToPut(int row) {
//如果最后一个皇后被放置完毕，将当前解复制到全部解中
if(row > ) {
for(int k = ; k < ; k ++)
record[count][k] = mark[k]; //因为要递归，所以count必须声明在函数外部
count ++;
} //在同一行上，逐一尝试将当前皇后放置在不同列上
for(int col=; col<=; col++) { // 递归结束条件：for循环8次，if条件都不满足，无法进入递归函数，递归结束，开始回溯
// 皇后所在的列坐标始终为 col
// 45度角坐标的'和'始终为 row+col
// 135度坐标的'和'始终为 row-col+9 (因为有可能出现负数，所以+9)
if(columnIsOk[col] && degree45IsOk [row + col] && degree135IsOk[row - col + ]) { // 能否放置皇后的条件，
mark[row] = col; // 放置皇后，mark数组对应的(row,col)坐标即一个皇后。这里将数组的(索引,值)抽象为坐标，值得学习。
columnIsOk[col] = degree45IsOk[row + col] = degree135IsOk[row - col + ] = false; // 控制三个方向
tryToPut(row + ); // 一行只能放一个皇后，所以下移一行，执行递归
// 其它代码都不重要，能把下面1行代码理解了就全部理解了
// 这一行存在的意义：递归结束，回溯遍历上一行
// 这就是递归，不是顺着来遍历的，而是倒着遍历的
columnIsOk[col] = degree45IsOk[row + col] = degree135IsOk[row - col + ] = true; // 撤销对3个方向的控制
} }
}
下面是我自己写的2n皇后的代码，不得不说看代码和写代码是两回事，看的时候觉得很好写，写起来各种出错，各种修改，最后缝缝补补，总算是通过了蓝桥杯的练习系统，
我用的是八皇后中第一种方法的扩展，虽然我写代码的时候思路很清晰，但写出来运行效率很低，运行时间长，以后还要改进，里面用的循环太多了，明天继续看看大神的答案再整理。
就是先下白棋和八皇后一个思路，然后每找到一个白棋的解 储存一下白棋解局，再重置棋盘（将黑棋子能下的地方全标为1）再下黑棋（和下白棋思路一样）每找到一个黑棋解或者循环完毕无解，就恢复白棋的棋局，继续回溯寻找白棋的解。
#include <iostream>
#include <cstdio>
using namespace std;
int count=;
int qipan[][],temp[][]; void fangheiqizi(int row,int n)//
{
if(row>=n)
{count++;
}
else{ for (int j=;j<n;j++)
if (qipan[row][j]==){
qipan[row][j]=-;
for (int k=row;k<n;k++)
for (int m=;m<n;m++)
if ((k==row||m==j||k+m==row+j||k-m==row-j)&&qipan[k][m]==)
qipan[k][m]=row+; fangheiqizi(row+,n); for (int k=row;k<n;k++)
for (int m=;m<n;m++)
if (qipan[k][m]==row+)
qipan[k][m]=;
qipan[row][j]=; }
} } void fangbaiqizi(int row,int n)//先放白棋，
{
if (row>=n){//每找到一个白棋的解储存下来 再重新布置棋局 再下黑棋 每找到一个黑棋的解或黑棋无解再恢复白棋的原来的局
for (int ii=;ii<n;ii++)
for (int jj=;jj<n;jj++)
{temp[ii][jj]=qipan[ii][jj];
if(qipan[ii][jj]!=-&&qipan[ii][jj]!=)qipan[ii][jj]=;
}
fangheiqizi(,n);
for (int ii=;ii<n;ii++)
for (int jj=;jj<n;jj++)
qipan[ii][jj]=temp[ii][jj]; }
else{ for (int j=;j<n;j++)
if (qipan[row][j]==){ qipan[row][j]=-;
for (int k=row;k<n;k++)
for (int m=;m<n;m++)
if ((k==row||m==j||(k+m==row+j)||(k-m==row-j))&&qipan[k][m]==)
qipan[k][m]=row+;
fangbaiqizi(row+,n);
// qipan[row][j]=1;
for (int k=row;k<n;k++)
for (int m=;m<n;m++)
if (qipan[k][m]==row+)
qipan[k][m]=;
qipan[row][j]=; } } }
int main()
{
int n;
cin>>n;
for (int i=;i<n;i++)
for (int j=;j<n;j++)
cin>>qipan[i][j];
fangbaiqizi(,n);
cout<<count; }
下面是大神答案。思路一样，方法可以看做八皇后中第三个方法的扩展，更简洁！不用考虑棋盘上的标记，只要额外两个数组来存储黑棋和白棋的解，判断点与点之间是否冲突就可以了
#include <cstdio>
#include<iostream>
using namespace std;
int chessb[][];//保存棋盘初始状态
int b[];//白皇后的放置位置 i行是第x列 b[i]=x;
int h[];//同上，不过是黑
int countn=;//计算方案数 int check(int queen[],int n)//判断同一列或者两对角线是否已经放置了
{
int i;
for (i = ; i < n; i++)
{
int judge=queen[i]-queen[n];
if(judge==||judge==i-n||judge==n-i)
{
return ;
}
}
return ; }
void bai(int line,int n)
{
int i;
if(line==n+)
{
countn++;
}
else
{
for(i=; i<=n; i++)
{
if(chessb[line][i]==&&i!=h[line])//可以放置
{
b[line]=i;
if(check(b,line))
{
bai(line+,n);
}
}
}
} } void hei(int line,int n)//黑皇后的搜索
{
int i;
if(line==n+) //黑皇后搜索完毕
{
bai(,n); //开始搜索白皇后
}
else
{
for(i=; i<=n; i++)
{
if(chessb[line][i]==)//可以放置
{
h[line]=i;
if(check(h,line))
{
hei(line+,n);
}
}
} }
} int main()
{
int n,i,j;
cin>>n;
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
scanf("%d",&chessb[i][j]);
}
}
hei(,n);
cout<<countn;
return ; ---------------------
作者：风卷云飞会天黑
来源：****
原文：https://blog.****.net/castledrv/article/details/44203633
版权声明：本文为博主原创文章，转载请附上博文链接！