题解 | #N皇后问题#

运行时间18ms,超过75%

public class Solution {
    int answer;
    public int Nqueen (int n) {
        int to=n+1;
        //ans[1]为第一个皇后所在位置, 依此类推
        int[] ans=new int[to];
        //加了ans[0]占位,第一个皇后就可以不用单独遍历
        ans[0]=Integer.MIN_VALUE;
        dfs(ans,1,to);
        return answer;
    }
    public void dfs(int[] now,int n,int to){
        if(n==to){
            answer++;
            return;
        }
        //第n个皇后依次判断能够放在0到to-1的位置i上
        for(int i=0;i<to-1;i++){
            boolean flag=true;
            //依次判断第0到第n-1个皇后j的位置与n是否冲突
            for(int j=0;j<n;j++){
                int sub=n-j;
                int indexJ=now[j];
                //列差==行差则在对角线上
                if(indexJ+sub==i||indexJ-sub==i||i==indexJ){
                    //有冲突则判断下一个位置i+1
                    flag=false;
                    break;
                }
            }
            if(flag){
                now[n]=i;
                dfs(now,n+1,to);
            }
        }
    }
}