AcWing 843. n-皇后问题

【题目描述】
AcWing 843. n-皇后问题

【思路】
cols[]标记数组标记哪些列被用过了
queens[i]存放第i个皇后放在哪一列了
发生对角线冲突的点横纵坐标之差相等

import java.util.Scanner;
import java.lang.Math;
public class Main{
    static int  N = 10;
    static char[][] g = new char[N][N];
    static boolean[]cols = new boolean[N];
    static int queens[] = new int[N];//保存每一行皇后的位置
    static int n;

    //检查对角线是否冲突
    public static boolean check(int x, int y){
        for(int i = 0; i < x; i ++)
            if( Math.abs(y -queens[i]) == Math.abs(x - i) )
                return false;
        return true;

    }

    public static void dfs(int x){
        //排列最后一行的皇后
        if(x == n){
            for(int i = 0; i < n; i ++){
                for(int j = 0; j < n; j ++)
                    System.out.print(g[i][j]+"");
                System.out.println();
            }
            System.out.println();   
            return;
        }

        //选择合适列
        for(int i = 0; i < n; i ++)
        {
            //(x, i)
            if(!cols[i] && check(x, i))
            {
                cols[i] = true;
                g[x][i] = 'Q';
                queens[x] = i;
                dfs(x + 1);
                g[x][i] = '.';
                cols[i] = false;
            }

        }


    }
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        n = reader.nextInt();
        for(int i = 0; i < N; i ++)
            for(int j = 0; j < N; j ++)
                g[i][j] = '.';
        dfs(0);

    }
}