[LeetCode]n-queens

题目传送门

题目描述：这道题要求在一个 (n x n) 的棋盘上放置 (n) 个皇后，使得任意两个皇后之间都不能互相攻击（即不能在同一行、同一列或同一对角线上），并返回所有满足条件的摆放方案；每个方案用由字符串组成的棋盘表示，其中 'Q' 表示皇后，'.' 表示空位，本质上是一个通过回溯搜索所有合法配置的组合问题。

代码：

class Solution {

    public List<List<String>> solveNQueens(int n) {
        boolean[] visitedColumns = new boolean[n];
        boolean[] visitedPositiveSlant = new boolean[n * 2];
        boolean[] visitedNegativeSlant = new boolean[n * 2];
        List<List<String>> result = new ArrayList<>();
        int[][] coordinate = new int[n][2];
        solveNQueens(result, n, visitedColumns, visitedPositiveSlant, visitedNegativeSlant, coordinate, 0,
                -1);
        return result;
    }

    private void solveNQueens(List<List<String>> result, int n, boolean[] visitedColumns,
                              boolean[] visitedPositiveSlant, boolean[] visitedNegativeSlant, int[][] coordinate, int queenCount,
                              int lastRow) {
        if (queenCount == n) {
            result.add(handleCoordinate(coordinate, n));
            return;
        }
        int row = lastRow + 1;
        for (int j = 0; j < n; j++) {
            if (!visitedColumns[j] && !visitedPositiveSlant[row - j + n - 1]
                    && !visitedNegativeSlant[row + j]) {
                visitedColumns[j] = true;
                visitedPositiveSlant[row - j + n - 1] = true;
                visitedNegativeSlant[row + j] = true;
                coordinate[queenCount][0] = row;
                coordinate[queenCount][1] = j;
                queenCount++;
                solveNQueens(result, n, visitedColumns, visitedPositiveSlant, visitedNegativeSlant,
                        coordinate, queenCount, row);
                queenCount--;
                visitedColumns[j] = false;
                visitedPositiveSlant[row - j + n - 1] = false;
                visitedNegativeSlant[row + j] = false;
            }
        }

    }

    private List<String> handleCoordinate(int[][] coordinate, int n) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < n; j++) {
                boolean isQueen = false;
                for (int k = 0; k < n; k++) {
                    int x = coordinate[k][0];
                    int y = coordinate[k][1];
                    if (x == i && y == j) {
                        isQueen = true;
                        break;
                    }
                }
                if (isQueen) {
                    stringBuilder.append("Q");
                } else {
                    stringBuilder.append(".");
                }
            }
            result.add(stringBuilder.toString());
        }
        return result;
    }
}

代码思路：按行逐步放置皇后，每次在当前行尝试所有列的位置，如果该位置所在列、主对角线（row - col）、副对角线（row + col）都没有被占用，就放置一个皇后，并标记对应列和对角线为已使用，然后递归处理下一行；如果后续无法继续放置，则撤销当前选择（回溯）并尝试下一个位置。当成功放置了 n 个皇后时，将记录的坐标转换为棋盘字符串加入结果。整个过程通过三个布尔数组快速判断冲突，从而高效剪枝，避免无效搜索。