leetcode-51. N 皇后

class Solution {
    public List<List<String>> solveNQueens(int n) {
        // 定义变量储存结果集
        List<List<String>> solutions = new ArrayList<List<String>>();
        // 定义跟传入的皇后个数一样多的整形数组
        int[] queens = new int[n];
        // 对数组全赋值为 -1
        Arrays.fill(queens, -1);
        // 定义三个集合分别记录每一列以及两个方向的每条斜线上是否有皇后
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        // 进行回溯
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        // 返回最终结果
        return solutions;
    }

    // 回溯的实现
    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        // 当皇后个数跟行数一样的时候证明符合条件且经排列完成
        if (row == n) {
            // 生成符合要求的棋盘布局
            List<String> board = generateBoard(queens, n);
            // 将本次解法加入结果集数组中
            solutions.add(board);
        } else {
            // 否则，判断哪一行那一列符合要求能放入皇后
            for (int i = 0; i < n; i++) {
                // 如果该列已经有了皇后则进行下一个 for 循环
                if (columns.contains(i)) {
                    continue;
                }
                // 如果还没有皇后，则判断斜线上是否有皇后
                int diagonal1 = row - i;
                // 如果该斜线上已经有了皇后则进行下一个 for 循环
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                // 如果还没有皇后，则判断另一个斜线上是否有皇后
                int diagonal2 = row + i;
                // 如果该斜线上已经有了皇后则进行下一个 for 循环
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }
                // 如果没有皇后，则确定这个位置符合放置皇后，将此时的行数作为数组的下标，列数作为该数组的对应行坐标的值存进去，记录入当前选择的位置
                queens[row] = i;
                // 记录入受影响的列和两个斜线
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                // 递归主体
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                // 还原当前选择的位置
                queens[row] = -1;
                columns.remove(i);
                // 还原受影响的列和两个斜线，让下一次通过层次的选择不受影响
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    // 生成结果棋盘的方法
    public List<String> generateBoard(int[] queens, int n) {
        // 定义存储棋盘的结果集
        List<String> board = new ArrayList<String>();
        // 生成棋盘的核心方法
        for (int i = 0; i < n; i++) {
            // 定义一个长度为皇后个数的 char 数组
            char[] row = new char[n];
            // 将其全部填充 '.'
            Arrays.fill(row, '.');
            // 再将上边记录皇后可以放的位置的对应地方用 'Q' 覆盖 '.'
            row[queens[i]] = 'Q';
            // 将 char 类型的数组转换为 String 类型添加到结果集中
            board.add(new String(row));
        }
        // 返回存储棋盘的结果集
        return board;
    }
}