蓝桥杯官网 试题 基础练习 2n皇后问题（DFS + 回溯）（8皇后问题变种）

题目大意：  给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

解题思路：  使用DFS遍历每个位置，判断是否能够插入黑皇后（或插入白皇后），若能，插入，遍历下一层；若不能，回溯至上一层。

//蓝桥杯官网 2n皇后问题
//Writed by Maolin Xiao,2020 03 08
//妇女节快乐！！！
#include<bits/stdc++.h>
using namespace std;

int map1[10][10];
int n;
int ans = 0;

int judge_b(int x,int y){
	for(int i = 0;i < n;i++){
		if(map1[x][i] == 2) return 0;
		if(map1[i][y] == 2) return 0;
		if(x - i >= 0 && y - i >= 0 && map1[x - i][y - i] == 2) return 0;
		if(x + i < n && y + i < n && map1[x + i][y + i] == 2) return 0;
		if(x - i >= 0 && y + i < n && map1[x - i][y + i] == 2) return 0;   
		if(x - i >= 0 && y + i < n && map1[x - i][y + i] == 2) return 0;   
	}
	return 1;
}

int judge_w(int x,int y){
		for(int i = 0;i < n;i++){
		if(map1[x][i] == 3) return 0;
		if(map1[i][y] == 3) return 0;
		if(x - i >= 0 && y - i >= 0 && map1[x - i][y - i] == 3) return 0;
		if(x + i < n && y + i < n && map1[x + i][y + i] == 3) return 0;
		if(x - i >= 0 && y + i < n && map1[x - i][y + i] == 3) return 0;   
		if(x - i >= 0 && y + i < n && map1[x - i][y + i] == 3) return 0;   
	}
	return 1;
}

void DFS(int x){
	if(x == n) {
		ans++;return;
	}
	for(int i = 0;i < n;i++){
		if(map1[x][i] == 1 && judge_b(x,i) == 1){
			for(int j = 0;j < n;j++){
				if(map1[x][j] == 1 && i != j && judge_w(x,j) == 1){
					map1[x][i] = 2;
					map1[x][j] = 3;
					DFS(x + 1);
					map1[x][j] = 1;
					map1[x][i] = 1;
				}
			}
		}
	}
}

int main(){
	cin>>n;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			cin>>map1[i][j];
		}
	}	
	DFS(0);
	cout<<ans<<endl;
	return 0;
}

如有疑问，欢迎联系2339814485（QQ）.