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

public class NQueens {

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    char[][] board = new char[n][n];
    // 初始化棋盘
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = '.';
        }
    }
    backtrack(res, board, 0);
    return res;
}

private void backtrack(List<List<String>> res, char[][] board, int row) {
    // 如果已经到达了最后一行，说明已经找到了一组解
    if (row == board.length) {
        res.add(construct(board));
        return;
    }
    int n = board[row].length;
    for (int col = 0; col < n; col++) {
        // 判断当前位置是否可以放置皇后
        if (!isValid(board, row, col)) {
            continue;
        }
        // 放置皇后
        board[row][col] = 'Q';
        // 递归到下一行
        backtrack(res, board, row + 1);
        // 回溯，撤销皇后的位置
        board[row][col] = '.';
    }
}

private boolean isValid(char[][] board, int row, int col) {
    int n = board.length;
    // 检查当前列是否有皇后互相冲突
    for (int i = 0; i < n; 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 < n; 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;
}

}