LeetCode52-N皇后II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/n-queens-ii/

中文链接：https://leetcode-cn.com/problems/n-queens-ii/

题目详述

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

上图为 8 皇后问题的一种解法。

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

题目详解

  • N 皇后问题。
  • LeetCode51-N皇后 是求解决方案，本题是求解决方案的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class LeetCode_00052 {

    public int totalNQueens(int n) {
        boolean[] col = new boolean[n];             // 当前列
        boolean[] dia1 = new boolean[2 * n - 1];    // 对角线 1 横纵坐标相加为定值
        boolean[] dia2 = new boolean[2 * n - 1];    // 对角线 2 横纵坐标相减为定值
        return dfs(n, 0, col, dia1, dia2);
    }

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