LeetCode 51. N皇后

51. N皇后

解题思路

通过col dg udg 三个布尔数据维护列，主对角线，反对角线是否已被皇后占据

• col[i] 表示第 i 列是否有皇后
• dg[i - j + n] 表示主对角线 (i - j) 是否有皇后
• udg[i + j] 表示反对角线 (i + j) 是否有皇后

参考代码

class Solution {
    private List<List<String>> result = new ArrayList<>();
    private boolean[] col;
    private boolean[] dg;
    private boolean[] udg;

    public List<List<String>> solveNQueens(int n) {
        col = new boolean[n];
        dg = new boolean[2 * n];
        udg = new boolean[2 * n];
        // 初始化棋盘
        char[][] board = new char[n][n];
        for(char[] row : board) {
            Arrays.fill(row, '.');
        }

        dfs(board, 0, n);
        return result;
    }

    /**
     * row 为当前行
     * n 为皇后数 / 棋盘的大小 / board.length
     */
    private void dfs(char[][] board, int row, int n) {
        // 终止条件
        if(row == n) {
            List<String> tmp = new ArrayList<>();
            for(char[] r : board) {
                tmp.add(new String(r));
            }
            result.add(tmp);
        }

        for(int i = 0; i < n; i ++) {
            // 判断列 主对角线 反对角线是否放置皇后
            if(!col[i] && !dg[row - i + n] && !udg[row + i]) {
                board[row][i] = 'Q';
                col[i] = dg[row - i + n] = udg[row + i] = true;
                dfs(board, row + 1, n);
                col[i] = dg[row - i + n] = udg[row + i] = false;
                board[row][i] = '.';
            }
        }
    }
}