蓝桥杯基础练习VIP-2n皇后问题 （C++代码）

解题思路:
【思路一】先在棋盘上放完白皇后，再在有白皇后的棋盘上放黑皇后。 先用dfs一个一个放白皇后，当到达递归边界时，说明白皇后已经放完，可以放黑皇后了，再调用第二个dfs放黑皇后。用二维数组checkboard[n][n]判断能否放皇后。

【思路二】因为两个皇后除了不能占用同一个棋格，互相不产生其他影响，所以先打印单个皇后（即n皇后）的所有棋盘摆放方案，有row个，然后从row个方案中选出两个方案组合在一起，相当于把一个已经放好白皇后的棋盘和一个已经放好黑皇后的棋盘合在一起。用二维数组temp[row][]存储, 二维数组的每一行表示一种方案，共有row种方案，约束条件是选中的两行数据每一列的数字都不能相同。

注意事项:

【思路二】最后要×2，先放白皇后后放黑皇后 和 先放黑皇后后放白皇后
参考代码:

/*-------------------------------思路一------------------------------*/
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1000;
int checkboard[maxn][maxn];  //棋盘
int vis1[3][maxn]; 
int vis2[3][maxn]; 
int n, tot = 0;

void search2(int cur){
	if(n == cur){ 
		tot++;
	} else{
		for(int i = 0; i < n; i++){
			if(checkboard[cur][i] == 1){
				if(!vis2[0][i] && !vis2[1][cur + i] && !vis2[2][cur - i + n]){
				vis2[0][i] = vis2[1][cur + i] = vis2[2][cur - i + n] = 1;
				search2(cur + 1);
				vis2[0][i] = vis2[1][cur + i] = vis2[2][cur - i + n] = 0;
				}	
			}					
		}
	}
} 

void print_qipan(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++)
			printf("%d ", checkboard[i][j]);
		printf("\n");
	}
	printf("------------------\n");
}

void search(int cur){
	if(n == cur){ 
		search2(0);
//		print_qipan();
//		tot++;
	} else{
		for(int i = 0; i < n; i++){
			if(checkboard[cur][i] == 1){
				if(!vis1[0][i] && !vis1[1][cur + i] && !vis1[2][cur - i + n]){
			//	C[cur] = i;          //打印棋盘时用到
				vis1[0][i] = vis1[1][cur + i] = vis1[2][cur - i + n] = 1;
				checkboard[cur][i] = 0;
				search(cur + 1);
				checkboard[cur][i] = 1;
				vis1[0][i] = vis1[1][cur + i] = vis1[2][cur - i + n] = 0;
				}	
			}					
		}
	}
}

int main (void){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			scanf("%d", &checkboard[i][j]);
		}
	}
	search(0);
	printf("%d",tot);
	return 0;
}



/*-------------------------------思路二------------------------------*/
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1000;
int checkboard[maxn][maxn];  //棋盘
int vis[3][maxn];  //判断是否合法 
int temp[maxn][maxn], C[maxn];   //temp是将棋盘转换成全排列数字的数组
int n, tot = 0, ting = 0;
int row = 0;          //temp数组的行数 
int *T;

void search(int cur){
	if(n == cur){ 
		for(int i = 0; i < n; i++){
			temp[row][i] = C[i];
		}
		row++;
	}
	else{
		for(int i = 0; i < n; i++){
			if(checkboard[cur][i] == 1){
				if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]){
				C[cur] = i;
				vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;
				search(cur + 1);
				vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
				}	
			}					
		}
	}
}

int main (void){
	
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			scanf("%d", &checkboard[i][j]);
		}
	}
	search(0);
	for(int i = 0; i < row; i++){
		T = temp[i];
		for(int j = i + 1; j < row; j++){
			int ok = 1;
			for(int k = 0; k < n; k++){
				if(temp[j][k] == T[k]){
					ok = 0;
					break;
				}
			}
			if(ok){
				tot++;
			}			
		}		
	}
	printf("%d",tot*2);
	return 0;
}