建议在看此问题之前，先弄懂n皇后问题
问题描述
给定一个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
#include <iostream> using namespace std; int n; int a[10][10]; int y[10],d1[20],d2[10]; int number; void dfs(int x,int z){ //z表示黑白皇后。1黑，2白 if(x==n && z==2){ //放到最后一行，并且白皇后放完结束 number++; return; } if(x==n){ dfs(0,z+1); //放完黑皇后，在放白皇后 return; } for(int i=0;i<n;i++){ //每一行的每一列 if(a[x][i] && y[i]!=3 && y[i]!=z && d1[x+i]!=3 && d1[x+i]!=z && d2[x-i+n]!=3 && d2[x-i+n]!=z){ a[x][i]=0; y[i]+=z; d1[x+i]+=z; d2[x-i+n]+=z; dfs(x+1,z); y[i]-=z; d1[x+i]-=z; d2[x-i+n]-=z; a[x][i]=1; } } } int main(){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>a[i][j]; } } dfs(0,1); //从第0行开始放 cout<<number; return 0; }
z=1时正在放黑皇后，z=2时正在放白皇后，
所以y[i]=0时黑白皇后都可放，z=1时不可放黑皇后，z=2时不可放白皇后，z=3时黑白皇后都不可放。换句话说只要不等于3并且不等于本身z就可以放当前要放的皇后种类。
