代码

class Solution {
    int n;
    boolean[] col,ne,nw;

    public int totalNQueens(int _n) {
        n = _n;
        col = new boolean[n];
        ne = new boolean[2 * n];
        nw = new boolean[2 * n];
        return dfs(0);
    }

    public int dfs(int depth){
        if(depth == n){
            return 1;
        }

        int res = 0;
        for(int i = 0; i < n; i++){
            if(!col[i] && !ne[depth-i+n] && !nw[i+depth]){
                col[i] = ne[depth-i+n] = nw[i+depth] = true;
                res += dfs(depth+1);
                col[i] = ne[depth-i+n] = nw[i+depth] = false;
            }
        }

        return res;
    }
}

关于dfs的返回值有点模糊,没太想明白

class Solution {

    boolean[] row, m, s;
    int n;

    public int totalNQueens(int _n) {

        // 这是一个有限制条件的dfs问题
        // 条件有3个: 行, 列, 主副对角线上不能有同时存在
        // 副对角线: (y-1) = -x => -1 = y+x
        // 主对角线: y - 1 = x => 1 = y-x

        n = _n;
        row = new boolean[n];
        m = new boolean[n * 2];
        s = new boolean[n * 2];

        // 参数2: 行, 参数3: 列
        return dfs(0);
    }

    public int dfs(int u){

        //由于是找到方案, 深度到达第n行时, 表示找到了一个方案.
        if(u == n){
            return 1;
        }

        //每一次开始dfs到一次dfs结束只有一个方案, 因些需要将一棵树的方案数初始化为0
        int res = 0;
        //对于每一个层, 会依次遍历1-n, 直到找到可以放置的位置时深入下一层
        for(int i = 0; i < n; i++){
            if(!row[i] && !m[i-u+n] && !s[i+u]){
                row[i] = m[i-u+n] = s[i+u] = true;
                res += dfs(u+1);
                row[i] = m[i-u+n] = s[i+u] = false;
            }
        }

        return res;
    }
}