Leetcode 51.N皇后

题目要求

  • 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

示例 1：

输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：
输入：n = 1
输出：[[“Q”]]

回溯法

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
class Solution {
    public List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        // board表示棋盘
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        backtrack(n, 0, board);
        return res;
    }

    public void backtrack(int n, int row, char[][] board) {
        // 当遍历到最后一行(n-1)后说明已经找到一个解法
        if (row == n) {
            // 用于将board转换成题目要求的格式
            List<String> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    sb.append(board[i][j]);
                }
                list.add(sb.toString());
            }
            res.add(list);
            return;
        }

        // 遍历当前行的每一列，尝试放置皇后
        for (int col = 0; col < n; col++) {
            // 判断在当前位置放置皇是否合法
            if (isLegal(row, col, board, n)){
                // 合法则放置皇后，并向下一行递归
                board[row][col] = 'Q';
                backtrack(n, row + 1, board);
                // 回溯，撤销放置的皇后
                board[row][col] = '.';
            }
        }
    }
    
    // 判断当前位置(row, col)放置皇后是否合法
    public boolean isLegal(int row, int col, char[][] board, int n) {
        // 检查当前列是否有皇后
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // 由于我们是从上往下放置皇后的，所以只需要检查上方的行的对角线即可
        // 检查左上对角线是否有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // 检查右上对角线是否有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
}