LeetCode 每日一题 24.12.2

52. N 皇后 II

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 9

回溯：

利用深度优先搜索，判断单个点是否符合条件，符合再递归下去，如果最后一个都满足，则算一种结果。复杂度O(N!)。

    static int[] chess;

    public static int totalNQueens(int n) {
        chess = new int[n];
        return dfs(0, n);
    }

    public static int dfs(int floor, int n) {
        if (floor == n) {
            return 1;
        }
        int sum = 0;
        for (int i = 0 ; i < n ; i++) {
            boolean flag = true;
            for (int j = 0 ; j < floor ; j++) {
                if (chess[j] == i || Math.abs(chess[j] - i) == Math.abs(j - floor)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                chess[floor] = i;
                sum += dfs(floor + 1, n);
            }
        }
        return sum;
    }