问题描述
给定一个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皇后问题的解法
#include<iostream>using namespace std;
int ans, q[8], n;
void Q(int row)
{
if (row == n) { ans++; }
else
{
for (int i = 0;i < n;i++) //遍历第row行第i列，看哪一个可以放下皇后
{
bool flag = true;
q[row] = i; //假设第row行的皇后放到i列，存起来
for (int j = 0;j < row;j++) //检查j行q[j]列的其他皇后是否跟新放入的兼容
{
if (q[j] == q[row] || q[j] + j == q[row] + row || q[j] - j == q[row] - row)
{
flag = false;
break;
}
}
if (flag)
Q(row + 1);
}
}
}
int main()
{
while (cin >> n)
{
ans = 0;
Q(0);
cout << ans << endl;
}
return 0;
}
回溯法，思路，因为每行必须放一个，所以就省去了一维，每次只探索列数
所以用Q(row)的递归深度代表行数，每次递归都探索该row行的全部列，放入皇后之后再检查跟上面行的皇后是否兼容，用q[8]存皇后的位置。
那么回到本题，2n皇后问题，从n皇后问题拓展，我们可以认为是放两次n皇后，也就是先放黑，满足n黑皇后问题后在之前的情况之下再做n白皇后问题。
#include<iostream>using namespace std;int n, ans;bool board[8][8];int q[8][2];//拓展一个长度来存白皇后位置void Q(int row, bool isBlack){ if (row == n&&isBlack) { Q(0, false); } if (row == n && !isBlack) { ans++; } if (isBlack) { for (int i = 0;i < n;i++) //测试第row行，第i列的位置 { if (board[row][i]) //此处可以放棋子 { q[row][0] = i; bool flag = true; for (int j = 0;j < row;j++) //测试第j行，q[j][0]列的黑皇后是否兼容 { if (q[row][0] == q[j][0] || row - q[row][0] == j - q[j][0] || row + q[row][0] == j + q[j][0]) { flag = false; break; } } if (flag) Q(row + 1, true); } } } else //白皇后 { for (int i = 0;i < n;i++) { if (board[row][i] && q[row][0] != i) { bool flag = true; q[row][1] = i; for (int j = 0;j < row;j++) { if (q[row][1] == q[j][1] || row - q[row][1] == j - q[j][1] || row + q[row][1] == j + q[j][1]) { flag = false; break; } } if (flag) Q(row + 1, false); } } }}int main(){ bool num; while (cin >> n) { ans = 0; for (int i = 0;i < n;i++) { for (int j = 0;j < n;j++) { cin >> num; board[i][j] = num; } } //地图存完了，开始遍历 Q(0, true); cout << ans << endl; } return 0;}因为题目要求，在探索棋盘时还要注意该位置是否可以放棋子（以及该位置有没有黑皇后）