首页 > 代码库 > 2N皇后问题

2N皇后问题

2024-09-10 12:14:13   215人阅读

问题描述
　　给定一个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 #include <cstdio> 2 #include <iostream> 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皇后问题还有几个高效的解法，采用非递归形式和位运算同样能求解。传送门

2N皇后问题


联系
我们