【Leetcode 每日一题】52. N 皇后 II

问题背景

$n$ 皇后问题 研究的是如何将 $n$ 个皇后放置在 $n\times n$ 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 $n$，返回 $n$ 皇后问题 不同的解决方案的数量。

数据约束

• $1\le n\le 9$

解题过程

只需要统计可能的结果数量，参考修改 昨天的题解 就可以。
在不需要输出路径的前提下，位运算实现的优势就非常明显了。直接标记需要路径数组来记录之前访问过的节点信息，用布尔型数组虽然不需要记录路径，也避免不了定义几个标记数组。

具体实现

直接判断

class Solution {
    public int totalNQueens(int n) {
        int[] path = new int[n];
        return dfs(0, n, path);
    }

    private int dfs(int i, int n, int[] path) {
        if(i == n) {
            return 1;
        }
        int res = 0;
        for(int j = 0; j < n; j++) {
            if(check(i, j, path)) {
                path[i] = j;
                res += dfs(i + 1, n, path);
                path[i] = 0;
            }
        }
        return res;
    }

    private boolean check(int i, int j, int[] path) {
        for(int k = 0; k < i; k++) {
            if(j == path[k] || Math.abs(i - k) == Math.abs(j - path[k])) {
                return false;
            }
        }
        return true;
    }
}

位运算限制

class Solution {
    public int totalNQueens(int n) {
        return dfs(n, (1 << n) - 1, 0, 0, 0);
    }

    private int dfs(int n, int mask, int col, int mainDiag, int subDiag) {
        if(col == mask) {
            return 1;
        }
        int limit = col | mainDiag | subDiag;
        int candidate = mask & (~limit);
        int cur;
        int res = 0;
        while(candidate != 0) {
            cur = candidate & (-candidate);
            candidate ^= cur;
            res += dfs(n, mask, col | cur, (mainDiag | cur) << 1, (subDiag | cur) >>> 1);
        }
        return res;
    }
}

数组标记

class Solution {
    public int totalNQueens(int n) {
        boolean[] col = new boolean[n];
        boolean[] mainDiag = new boolean[2 * n - 1];
        boolean[] subDiag = new boolean[2 * n - 1];
        return dfs(0, n, col, mainDiag, subDiag);
    }

    private int dfs(int i, int n, boolean[] col, boolean[] mainDiag, boolean[] subDiag) {
        if(i == n) {
            return 1;
        }
        int res = 0;
        for(int j = 0; j < n; j++) {
            if(!col[j] && !mainDiag[i + j] && !subDiag[i - j + n - 1]) {
                col[j] = mainDiag[i + j] = subDiag[i - j + n - 1] = true;
                res += dfs(i + 1, n, col, mainDiag, subDiag);
                col[j] = mainDiag[i + j] = subDiag[i - j + n - 1] = false;
            }
        }
        return res;
    }
}