问题描述
给定一个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
1 #include2 #include 3 using namespace std; 4 const int maxn = 1000; 5 int G[maxn][maxn]; 6 int BQ[maxn]; 7 int WQ[maxn]; 8 int n; 9 int count = 0;10 void BlackQueue(int k){11 for(int i = 0; i < k - 1; i++){12 int judge = BQ[i] - BQ[k-1];13 if(judge == 0 || judge == k - 1 - i || -judge == k - 1 - i)14 return;15 }16 if(k == n){17 count++;18 return; 19 }20 for(int i = 0; i < n; i++){21 if(G[k][i]==1){22 G[k][i] = 3;23 BQ[k] = i;24 BlackQueue(k+1);25 G[k][i] = 1;26 }27 }28 }29 void WhiteQueue(int k){30 for(int i = 0; i < k - 1; i++){31 int judge = WQ[i] - WQ[k-1];32 if(judge == 0 || judge == k - 1 - i || -judge == k - 1 - i)33 return;34 }35 if(k == n){36 BlackQueue(0);37 return;38 }39 for(int i = 0; i < n; i++){40 if(G[k][i]==1){41 G[k][i] = 2;42 WQ[k] = i;43 WhiteQueue(k+1);44 G[k][i] = 1;45 }46 }47 } 48 int main(){49 cin >> n;50 for(int i = 0; i < n; i++){51 for(int j = 0; j < n; j++){52 scanf("%d", &G[i][j]);53 }54 }55 WhiteQueue(0);56 cout << count << endl;57 return 0;58 }
另外N皇后问题还有几个高效的解法，采用非递归形式和位运算同样能求解。