N皇后51

N皇后

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        // 每一行
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(".");
            }
            board.add(sb.toString());
        }

        backtrack(board, 0);
        return res;
    }

    // 第row行放置皇后的位置
    public void backtrack(List<String> board, int row) {
        // 回溯完了，返回一种结果
        if (row == board.size()) {
            res.add(new ArrayList<>(board));
            return;
        }

        // 尝试放在不同列
        for (int cel = 0; cel < board.size(); cel++) {
            if (!isValid(board, row, cel)) {
                continue;
            }

            // 选择放置在第row行第cell列
            board.set(row, board.get(row).substring(0, cel) + 'Q' + board.get(row).substring(cel + 1));
            backtrack(board, row + 1);
            // 撤销选择
            board.set(row, board.get(row).substring(0, cel) + '.' + board.get(row).substring(cel + 1));
        }
    }

    // 一共8种情况只需要考虑三种
    public boolean isValid(List<String> board, int row, int cel) {
        // 同一列是否存在皇后
        for (int i = row - 1; i >= 0; i--) {
            if (board.get(i).charAt(cel) == 'Q') {
                return false;
            }
        }

        // 左上角是否存在皇后
        for (int i = row - 1, j = cel - 1; i >= 0 && j >= 0; i--, j--) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        // 右上角是否存在皇后
        for (int i = row - 1, j = cel + 1; i >= 0 && j < board.size(); i--, j++) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        return true;
    }
}

性能提升版本

/**
 * 正对角线上row和cel相等，所以判断在不在正对角线上需要用row-cel，可能出现负值，所以加上n，取值范围变成了[-n, n]反对角线上row+cel==n,取值范围[0, 2n]
 * 
 **/
class Solution {
    List<List<String>> res = new ArrayList<>();
    
    public List<List<String>> solveNQueens(int n) {
        // 记录同一列有没有皇后
        boolean[] cols = new boolean[n];
        // 记录正对角线（左上到右下）有没有皇后
        boolean[] diag1 = new boolean[2 * n];
        // 记录反对角线有没有皇后
        boolean[] diag2 = new boolean[2 * n];
        char[][] board = new char[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }

        backtrack(board, 0, cols, diag1, diag2);
        return res;
    }

    private void backtrack(char[][] board, int row, boolean[] cols, boolean[] diag1, boolean[] diag2) {
        if (row == board.length) {
            res.add(construct(board));
            return;
        }

        for (int col = 0; col < board.length; col++) {
            int d1 = row - col + board.length;  // 转换成正数
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) {
                continue;
            }

            board[row][col] = 'Q';
            cols[col] = true;
            diag1[d1] = true;
            diag2[d2] = true;

            backtrack(board, row + 1, cols, diag1, diag2);

            board[row][col] = '.';
            cols[col] = false;
            diag1[d1] = false;
            diag2[d2] = false;
        }
    }

    private List<String> construct(char[][] board) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            res.add(new String(board[i]));
        }
        return res;
    }
}