蓝桥杯vip试题 基础练习 2n皇后问题（java实现）_白皇后算法java实现

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

　　给定一个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

我的分析：这里的2n皇后（黑白两个）和n皇后问题确实没太大区别，这里就从n皇后问题开始分析。这里它要求棋盘是随机地摆放0和1，所以还是得用个二维数组来表示棋盘，数组元素就存储0或1，黑或白。这个问题按经典算法分为两个部分，如何查找和如何判断。如何查找就是怎样遍历完整个棋盘，找到确定位置；如何判断就是怎样判断当前位置是“正确”的。

我们可以从第一个位置开始检索，从左到右，从上到下。因为要求不能在同一行，所以在当前行找到位置后就可以直接跳转到下一行 查找下一行的位置。因为每一行都是从第一个开始检索并且找到后就立即跳到下一行，所以不用判断同一行是否有相同皇后。我们只需要判断图中的三条红线，即列、左对角线和右对角线。又因为从左到右、从上到下的检索顺序，所以我们只用判断“前半部分”，后面的都还没有检索，所以肯定没有相同元素。如何判断就这样啦，接下来仔细思考如何查找。

用回溯的话，它是检索到了位置不对的地方，就马上回到上一行更变位置。比如我现在找到了第3行，但是每一列的位置都与上面摆好的位置冲突，我们这时就要回退到第2行，假设第2行第4列是之前摆好的，所以我们就是回退到（2，4），然后移到下一个位置也就是（2，5），不能往前移，因为前面的位置都是与上面的位置不符的，所以只能往后移，后面的都是没有检索过的位置。每次回退后，（2，4）这个原位置就要变回1，因为它已经不被我们所用，要及时变回原样。还有就是，当黑白皇后都摆好后，这时count++，函数也要回退，回退摆好的位置就会变为1，因为我们还要找新的摆放位置，所以这是必要的。我最开始还有个疑惑，黑的先还是白的先，黑白位置互换又是一种新的摆法，岂不是最后结果还要乘2？但是回溯的精妙之处解决了这些问题。回退是从后往前回退，第5行的所有可能找完后，它会回退到第4行，又换新的位置摆放，就这样它会回退到最初的第一行第一列这个位置，然后移到（1，2）这个又找新的摆放位置，这样的话，假设我们白的先，（1，1）刚才是被白的占了，现在白的移到（1，2），那么黑的就有机会移到（1，1）这个位置，所以我之前的顾虑黑白位置互换又乘2，是完全不用的。回溯法真的很暴力，它遍历了所有的可能性，以至于保证了我们结果的准确性。这里我们规定2表示白皇后，3表示黑皇后。

import java.util.Scanner;
 
public class Main {
	//用来存放棋盘
	static int[][] chessboard;
	//棋盘的“阶数”
	static int n;
	//皇后摆放的种类次数
	static int count;
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		chessboard = new int[n][n];
		for (int i = 0; i < n; i++) 
			for (int j = 0; j < n; j++) 
				chessboard[i][j] = in.nextInt();
		
		//默认从第0行开始，先找白皇后
		dfs(0, 2);
		System.out.println(count);
		in.close();
	}
	
	/**
	 * 判断当前位置是否能放
	 * @param x 行坐标
	 * @param y 列坐标
	 * @param type 是白是黑
	 * @return
	 */
	public static boolean check(int x, int y, int type) {
		if (chessboard[x][y] != 1) 
			return false;
		
		//判断当前列上是否有相同皇后
		for (int i = 0; i < x; i++) 
			if (chessboard[i][y] == type) 
				return false;
		
		//判断右对角线上是否有相同元素
		for (int i = x - 1, j = y + 1; i > -1 && j < n; i--, j++) 
			if (chessboard[i][j] == type) 
				return false;
			
		//判断左对角线上是否有相同元素
		for (int i = x - 1, j = y - 1; i > -1 && j > -1; i--, j--) 
			if (chessboard[i][j] == type) 
				return false;
			
		return true;
	}
	
	/**
	 * 摆放位置可以看作是找一条“通路”，当前位置不行就回退用dfs（回溯法）
	 * @param row 棋盘的行数
	 * @param type 2表示白皇后，3表示黑皇后
	 */
	public static void dfs(int row, int type) {
		//最后一行判断
		if (row == n) {
			if (type == 2) //如果白皇后确定好位置就开始摆黑皇后位置
				dfs(0, 3);
			else//若黑皇后摆好次数就加1
				count++;
			return;
		}
		//i表示列数，行数通过递归增长
		for (int i = 0; i < n; i++) 
			if (check(row, i, type)) {
				chessboard[row][i] = type;
				//这一行找好后就直接去下一行找
				dfs(row + 1, type);
				//找完回退到这里，这个位置就变成原样，为了找新的摆放位置
				chessboard[row][i] = 1;
			}
	}
 
}