题解 | #N皇后问题#

import java.util.*;
public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */

     /**
        思路：
        1.利用递归 递归成功进入下一行
        2.递归终止条件 已经成功到达第n行 也就是前面n行都成功放入了  最终目标达成才能return 后面的代码不需要再执行 而没有完成目标的 后面的代码还需要执行。
        3.j 和 i-j 和 i+j 分别可以确定 列 正斜 反斜  
        用三个hashSet来判断是否还能放入    
     
      */


    int res = 0;  
    HashSet<Integer> column = new HashSet<>();
    HashSet<Integer> posSlant = new HashSet<>();
    HashSet<Integer> conSlant = new HashSet<>();
    public int Nqueen (int n) {
        // write code here
        //从第0行开始
        compute(0,n);
        return res;
    }

    void compute(int i ,int n){
        if(i == n){
        //递归终止 不需要再往下面运行
            res++;
            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);
            //开始递归下一行
            compute(i+1,n);
            //递归结束 接触限制条件
            conSlant.remove(i+j);
            posSlant.remove(i-j);
            column.remove(j);
        }
    }
}