问题描述
给定一个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皇后问题的变形，假设先排黑皇后，那么对于黑皇后来时就是单纯的n皇后问题，唯一的区别的就是某个位置上不能放皇后而已。
第二步排白皇后，那么对于白皇后来说就是就是单纯的n皇后问题，唯一的区别的就是某个位置上不能放皇后而已，这个不能放包含（题目给的值为0的位置和已经放置黑皇后的位置）。
如果不明白n皇后问题，请看我的另一篇博文-n皇后问题，相信你能看明白的
#include<iostream> #include <math.h> int N; using namespace std; int chess[8][8]; int num=0;//用来记录总的放置个数 int blackCur[8];//此全局变量是用来记录黑皇后的第i行放在得第j列，其中下标为i，值为j int whiteCur[8];//此全局变量是用来记录白皇后的第i行放在得第j列，其中下标为i，值为j int check(int n,int Cur[]){//传进来行 for(int i=0;i<n;i++){ if( Cur[i] == Cur[n] || abs(n-i) == abs(Cur[n] - Cur[i]) ){//判断当前放置的位置是否与之前的放置位置是否在同一列或同斜列 return 0; } } return 1; } void whiteQueen(int n){ if(n==N){ num++; }else{ for(int j=0;j<N;j++){ if( blackCur[n]!=j && chess[n][j]!=0){ whiteCur[n]=j; if(check(n,whiteCur)){ whiteQueen(n+1); } } } } } void blackQueen(int n){ if(n==N){//如果找到了最后一行的下一行，那么就可以将次数+1了(就是之前把所有的行已经放完了，数组下标从0开始的勿忘) whiteQueen(0);//黑皇后放置成功开始放置白皇后 }else{ for(int j=0;j<N;j++){//列的位置从0往最后放置 if(chess[n][j]!=0) { blackCur[n]=j;//记录下当前行的当前列 if(check(n,blackCur)){//判断当前放置的行列是否合适 blackQueen(n+1);//开始进行下一行的放置 } } } } } int main(){ cin>>N; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ cin>>chess[i][j]; } } blackQueen(0); cout<<num; return 0; }
