题解 | #N皇后问题#

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int count;
    Set<Integer> column = new HashSet<Integer>(); //标记列不可用
    Set<Integer> posSlant = new HashSet<Integer>();//标记正斜线不可用
    Set<Integer> conSlant = new HashSet<Integer>();//标记反斜线不可用
    public int Nqueen (int n) {
        // write code here
        //简化思路，其实无需数组来表示这个棋盘，关键在于棋盘的当前列和棋盘的左上和右上无皇后
        //（因为是从上往下遍历的，所以此时无需考虑左下和右下），可以改用3个set集合来保存已被选中
        //的列集和不可用的正斜线和反斜线
//         dfs1(0,n);
//         return count;
        
//         //由第一层开始向下递归遍历所有可能，判断是否满足条件
        count=0;
        int[][] nums=new int[n][n];
        dfs(nums,0,n);
        return count;
    }
    private void dfs1(int i,int n){
        if(i==n){
            count++;
            return;
        }
        for(int j=0;j<n;j++){
            if(column.contains(j)||posSlant.contains(i-j)||conSlant.contains(i+j)){
                continue;
            }
            column.add(j);
            posSlant.add(i-j);
            conSlant.add(i+j);
            dfs1(i+1,n);
            column.remove(j);
            posSlant.remove(i-j);
            conSlant.remove(i+j);
        }
        
    }
    private void dfs(int[][] nums,int row,int n){
        if(row==n){
            count++;
            return;
        }
        for(int i=0;i<n;i++){
            nums[row][i]=1;
            if(isRight(nums,row,i)){
                dfs(nums,row+1,n);
            }
            nums[row][i]=0;
        }
    }
    private boolean isRight(int[][] nums,int row,int col){
        for(int i=0;i<row;i++){
            if(nums[i][col]==1){
                return false;
            }
        }
        int n=nums.length;
        for(int i=1,len=Math.max(row,col);i<=len;i++){
            if(inArea(row-i,col-i,n)&&nums[row-i][col-i]==1){
                return false;
            }
            if(inArea(row-i,col+i,n)&&nums[row-i][col+i]==1){
                return false;
            }
        }
        
        return true;
    }
    private boolean inArea(int i,int j,int n){
        return i>=0&&i<n&&j>=0&&j<n;
    }
}