LeetCode51-N皇后

发表于 | 分类于

题目链接

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

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

题目详述

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

img

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

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

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

题目详解

DFS，回溯。本题与 LeetCode37-解数独 类似，只不过摆放规则不一样，解题思路是一致的。

  • 检查是否合法。

  • 改变当前状态。

  • 进入下一层。
  • 退出下一层后进行恢复。
  • 成功的条件是整个棋盘被正确设置，也就是沿着一行一行移动后跃出棋盘。
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class LeetCode_00051 {

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] cs = new char[n][n];
        for (int i = 0; i < cs.length; ++i) {
            Arrays.fill(cs[i], '.');
        }
        dfs(cs, 0, res);
        return res;
    }

    private void dfs(char[][] cs, int r, List<List<String>> res) {
        int n = cs.length;
        if (r == n) {
            List<String> list = new ArrayList<>(n);
            for (int i = 0; i < n; ++i) {
                list.add(new String(cs[i]));
            }
            res.add(list);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (isValid(cs, r, i)) {
                cs[r][i] = 'Q';
                dfs(cs, r + 1, res);
                cs[r][i] = '.';
            }
        }
    }

    /**
     * 检查是否合法（横竖斜不重复）
     * @param cs 棋盘
     * @param r  当前行
     * @param c  当前列
     * @return   合法为 true，否则为 false
     */
    private boolean isValid(char[][] cs, int r, int c) {
        int j = c;
        for (int i = r - 1; i >= 0; --i) {
            if (cs[i][j] == 'Q') {
                return false;
            }
        }
        j = c - 1;
        for (int i = r - 1; i >= 0 && j >= 0; --i) {
            if (cs[i][j--] == 'Q') {
                return false;
            }
        }
        j = c + 1;
        for (int i = r - 1; i >= 0 && j < cs.length; --i) {
            if (cs[i][j++] == 'Q') {
                return false;
            }
        }
        return true;
    }
}
  • 可以换一种方法检查是否合法。
  • 观察发现，对角线 1 横纵坐标相加为定值，对角线 2 横纵坐标相减为定值，那么对应的值可以代表那条对角线。
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
29
30
31
32
33
34
35
36
37
38
39
40
public class LeetCode_00051 {

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] cs = new char[n][n];
        boolean[] col = new boolean[n];             // 当前列
        boolean[] dia1 = new boolean[2 * n - 1];    // 对角线 1 横纵坐标相加为定值
        boolean[] dia2 = new boolean[2 * n - 1];    // 对角线 2 横纵坐标相减为定值
        for (int i = 0; i < cs.length; ++i) {
            Arrays.fill(cs[i], '.');
        }
        dfs(cs, 0, res, col, dia1, dia2);
        return res;
    }

    private void dfs(char[][] cs, int r, List<List<String>> res, boolean[] col, boolean[] dia1, boolean[] dia2) {
        int n = cs.length;
        if (r == n) {
            List<String> list = new ArrayList<>(n);
            for (int i = 0; i < n; ++i) {
                list.add(new String(cs[i]));
            }
            res.add(list);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (!col[i] && !dia1[r + i] && !dia2[r - i + n - 1]) {
                cs[r][i] = 'Q';
                col[i] = true;
                dia1[r + i] = true;
                dia2[r - i + n - 1] = true;
                dfs(cs, r + 1, res, col, dia1, dia2);
                cs[r][i] = '.';
                col[i] = false;
                dia1[r + i] = false;
                dia2[r - i + n - 1] = false;
            }
        }
    }
}