蓝桥杯基础练习VIP-2n皇后问题(java)

解题思路:
先找到全部黑皇后的位置并用数组记录下来 sec[i]= col,便于判断同列正副对角线,下标i表示黑皇后所在行,其值sec[i]表示所在列, 同理 dex[i]= col 表示白皇后的位置,不同颜色的皇后不同的递归参数.

注意事项:
当黑皇后全找到后,递归找白皇后,要从第一列(下标为0)开始找,能全部放下就count++;
参考代码:

import java.util.Scanner;

public class Main {
	static int[][] cheass; //棋盘
	static  int[] sec ; //黑皇后所在位置
	static int[] dex;//白皇后所在位置
	static int hhh = 2;//黑皇后
	static int bhh = 3;//白皇后
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		cheass = new int[n][n];
		for (int i = 0; i < cheass.length; i++) {
			for (int j = 0; j < cheass[i].length; j++) {
				cheass[i][j] = sc.nextInt();
			}
		}
		sec = new int[n];//黑皇后所在位置
		dex = new int[n];//白皇后所在位置
		dfs(hhh,sec,0);//先放置黑皇后
		System.out.println(count);
	}
	static int count=0;
	private static void dfs(int color , int[] address, int row) {
		if(row == address.length) { //表示有某个颜色的皇后全部放置完成
			if(color == hhh){ //如果颜色是黑色
				dfs(bhh,dex,0); //就继续放置白皇后
			}else{
				count++; //反之,如果是白皇后代表黑皇后能够全放置,白皇后也能全放下, 计数就加 1;
			}
			return; 
		}
		for (int i = 0; i < sec.length; i++) {
			if(cheass[row][i] == 1 && check(address,row,i) ){
				address[row] = i; //记录color皇后的位置
				cheass[row][i] = color;//记录该位置已有皇后
				dfs(color,address,row+1);//继续找下一列
				cheass[row][i] = 1;//回溯
			}
			
		}
	}
	private static boolean check(int[] address, int row, int col) {
		for (int j = 0; j < row; j++) {
			if(address[j] == col)return false;//判断同列
			if(address[j]+j == row+col)return false; //判断副对角线
			if(address[j]-j == col-row) return false;//判断正对角线
		}
		return true;
	}

}