LeetCode51-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
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
List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        cols = new int[n];
        //从第0行开始摆
        place(0);
        return res;
    }

    int[] cols;

    //在row位置摆放皇后
    void place(int row) {
        if (row == cols.length) {
            res.add(show());
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            if (isValid(row, col)) {
                cols[row] = col;
                place(row + 1);
            }
        }
    }

    //row行 col列是否可以摆放
    boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 第col列已经有皇后
            if (cols[i] == col) {
                return false;
            }
            // 第i行的皇后跟第row行第col列格子处在同一斜线上
            if (row - i == Math.abs(col - cols[i])) {
                return false;
            }
        }
        return true;
    }

    List<String> show() {
        List<String> list = new ArrayList<>();
        for (int row = 0; row < cols.length; row++) {
            StringBuffer buffer = new StringBuffer();
            for (int col = 0; col < cols.length; col++) {
                if (cols[row] == col) {
                    buffer.append("Q");
                } else {
                    buffer.append(".");
                }
            }
            list.add(buffer.toString());
        }
        return list;
    }

优化

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
61
62
63
64
65
66
67
68
69
70
71
72
73
List<List<String>> res = new ArrayList<>();

    /**
     * 数组索引是行号，数组元素是列号
     */
    int[] queens;
    /**
     * 标记着某一列是否有皇后
     */
    boolean[] cols;
    /**
     * 标记着某一斜线上是否有皇后（左上角 -> 右下角）
     */
    boolean[] leftTop;
    /**
     * 标记着某一斜线上是否有皇后（右上角 -> 左下角）
     */
    boolean[] rightTop;

    public List<List<String>> solveNQueens(int n) {
        if (n < 1) return res;
        queens = new int[n];
        cols = new boolean[n];
        leftTop = new boolean[(n << 1) - 1];
        rightTop = new boolean[leftTop.length];
        place(0);
        return res;
    }

    /**
     * 从第row行开始摆放皇后
     *
     * @param row
     */
    void place(int row) {
        if (row == cols.length) {
            res.add(show());
            return;
        }

        for (int col = 0; col < cols.length; col++) {
            if (cols[col]) continue;
            int ltIndex = row - col + cols.length - 1;
            if (leftTop[ltIndex]) continue;
            int rtIndex = row + col;
            if (rightTop[rtIndex]) continue;

            queens[row] = col;
            cols[col] = true;
            leftTop[ltIndex] = true;
            rightTop[rtIndex] = true;
            place(row + 1);
            cols[col] = false;
            leftTop[ltIndex] = false;
            rightTop[rtIndex] = false;
        }
    }

    List<String> show() {
        List<String> list = new ArrayList<>();
        for (int row = 0; row < cols.length; row++) {
            StringBuffer buffer = new StringBuffer();
            for (int col = 0; col < cols.length; col++) {
                if (queens[row] == col) {
                    buffer.append("Q");
                } else {
                    buffer.append(".");
                }
            }
            list.add(buffer.toString());
        }
        return list;
    }