题目描述

题目链接

https://leetcode.cn/problems/n-queens/

思路

「皇后问题」研究的是如何将个皇后放置在的棋盘上，并且使皇后彼此间不能相互攻击。皇后的走法是：可以横直斜走，格数不限。因此要求皇后彼此间不能相互攻击，等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。

直观的做法是暴力枚举将个皇后放置在的棋盘上的所有可能的情况，并对每一种情况判断是否满足皇后彼此之间不相互攻击。但暴力枚举的时间复杂度是非常高的，因此必须利用限制条件加以优化。显然，每个皇后必须位于不同行和不同列，因此将个皇后放置在的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。因此，可以通过回溯的方式寻找可能的解。

回溯的做法是：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后。每次新放置的皇后都不能和已经放置的皇后之间有攻击：即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并更新数组中的当前行的皇后列下标。当个皇后都放置完毕，则找到一个可能的解。当找到一个可能的解之后，将数组转换成表示棋盘状态的列表，并将该棋盘状态的列表加入返回列表。

由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有列可选择，第二个皇后最多有列可选择，第三个皇后最多有列可选择（如果考虑到不能在同一条斜线上，可能的选择数量更少），因此所有可能的情况不会超过种，遍历这些情况的时间复杂度是。

为了降低总时间复杂度，每次放置皇后时需要快速判断每个位置是否可以放置皇后，显然，最理想的情况是在的时间内判断该位置所在的列和两条斜线上是否已经有皇后。我们通过使用「集合」对皇后的放置位置进行判断，这样就可以在的时间内判断一个位置是否可以放置皇后。

基于集合的回溯
为了判断一个位置所在的列和两条斜线上是否已经有皇后，我们可以使用三个集合、和分别记录每一列以及两个方向的每条斜线上是否有皇后。

列的表示法很直观，一共有列，每一列的下标范围从到，使用列的下标即可明确表示每一列。

如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标间的关系。比如从左上到右下的这个方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如和就是在该方向的斜线上。因此使用行下标与列下标之差即可明确表示从左上到右下方向的斜线。

而从右上到左下方向的斜线，同一条斜线上的每个位置满足行下标与列下标之和相等，例如和就是在该方向的斜线上。因此使用行下标与列下标之和即可明确表示从右上到左下方向的斜线。

每次放置皇后时，对于每个位置判断其是否在这三个集合中，如果这三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

代码实现

public List<List<String>> solveNQueens(int n) {
    List<List<String>> ans = new ArrayList<>();
    // queens用来存储皇后位置
    int[] queens = new int[n];
    Arrays.fill(queens, -1);
    // 回溯
    backtrack(ans, queens, n, 0);
    return ans;
}
private final Set<Integer> columns = new HashSet<>();
private final Set<Integer> diagonals1 = new HashSet<>();
private final Set<Integer> diagonals2 = new HashSet<>();
private void backtrack(List<List<String>> ans, int[] queens, int n, int row) {
    // 遍历完最后一行时，保存当前棋盘
    if (row == n) {
        List<String> board = generateBoard(queens, n);
        ans.add(board);
        return;
    }
    // 遍历当前行的每一列
    for (int column = 0; column < n; column++) {
        // 过滤不符合放棋子的位置
        if (columns.contains(column)) {
            continue;
        }
        int diagonal1 = row - column;
        if (diagonals1.contains(diagonal1)) {
            continue;
        }
        int diagonal2 = row + column;
        if (diagonals2.contains(diagonal2)) {
            continue;
        }
        // 在当前行的column列处放置一颗棋子
        queens[row] = column;
        columns.add(column);
        diagonals1.add(diagonal1);
        diagonals2.add(diagonal2);
        // 处理下一行
        backtrack(ans, queens, n, row + 1);
        // 回溯
        queens[row] = -1;
        columns.remove(column);
        diagonals1.remove(diagonal1);
        diagonals2.remove(diagonal2);
    }
}
public List<String> generateBoard(int[] queens, int n) {
    List<String> board = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        char[] row = new char[n];
        Arrays.fill(row, '.');
        row[queens[i]] = 'Q';
        board.add(new String(row));
    }
    return board;
}

复杂度分析

• 时间复杂度：，其中是皇后数量。
• 空间复杂度：，其中是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过，数组的长度为，每个集合的元素个数也都不会超过。