[LeetCode]N-Queens II

Question
Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

本题难度Hard。

【思路】
​N-Queens​​中返回棋盘变成了解的个数。不必多说。

【代码】

public class Solution {
    int ans=0;
    public int totalNQueens(int n) {
        //require
        if(n<=0)
            return ans;
        //create 
        int[] nqueens=new int[n];
        //invariant
        dfs(nqueens,n,0);
        //ensure
        return ans;
    }

    private boolean isValid(int[] nqueens,int step){
        for(int i=0;i<step;i++){
            if(nqueens[i]==nqueens[step]||Math.abs(nqueens[i]-nqueens[step])==(step-i))
                return false;
        }
        return true;
    }

    private void dfs(int[] nqueens,int n,int step){
        //base case
        if(step>n-1){
            ans++;
            return;
        }

        for(int i=0;i<n;i++){
            nqueens[step]=i;
            if(isValid(nqueens,step))
                dfs(nqueens,n,step+1);
        }

    }
}

参考

​​N-Queens​​