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

import java.util.Arrays;
import java.util.Scanner;

public class 皇后问题_2n {
    //先方白皇后，再放黑皇后  白皇后标记为2，黑皇后标记为3
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        dfs(0, 2);
        System.out.println(ans);
    }

    static int ans = 0;
    
    public static void dfs(int n, int d) {
        if (n == arr.length) {
            if (d == 3) {
                ans++;
            }
            dfs(0, 3);
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[n][i] == 1 && arr[n][i] != 2) {
                arr[n][i] = d;
                if (check(n, i)) {
                    dfs(n + 1, d);
                }
                arr[n][i] = 1;//回溯
            }
        }
    }

    public static boolean check(int x, int y) {
        //判断是否在同一列
        for (int i = 0; i < x; i++) {
            if (arr[i][y] == arr[x][y]) {
                return false;
            }
        }
        //判断左斜上方是否有冲突
        for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
            if (arr[i][j] == arr[x][y]) {
                return false;
            }
        }
        //判断右斜上方是否有冲突
        for (int i = x - 1, j = y + 1; i >= 0 && j < arr.length; i--, j++) {
            if (arr[i][j] == arr[x][y]) {
                return false;
            }
        }
        return true;
    }

    static int[][] arr;

}