N皇后问题 Java 回溯法解题代码示例

class Solution { public List<List> solveNQueens(int n) { List<List> res = new ArrayList<>(); if (n <= 0) return res; char[][] board = new char[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(board[i], '.'); } dfs(res, board, 0); return res; }

private void dfs(List<List<String>> res, char[][] board, int row) {
    if (row == board.length) {
        res.add(construct(board));
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            dfs(res, board, row + 1);
            board[row][col] = '.';
        }
    }
}

private boolean isValid(char[][] board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

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

}