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

public class NQueens {

public static void main(String[] args) {
    NQueens nQueens = new NQueens();
    int n = 4;
    nQueens.solveNQueens(n);
}

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    int[] queens = new int[n];
    Arrays.fill(queens, -1);
    backtrack(result, queens, n, 0);
    return result;
}

private void backtrack(List<List<String>> result, int[] queens, int n, int row) {
    if (row == n) {
        result.add(generateBoard(queens, n));
        return;
    }
    for (int i = 0; i < n; i++) {
        if (isValid(queens, n, row, i)) {
            queens[row] = i;
            backtrack(result, queens, n, row + 1);
            queens[row] = -1;
        }
    }
}

private boolean isValid(int[] queens, int n, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (queens[i] == col || Math.abs(row - i) == Math.abs(col - queens[i])) {
            return false;
        }
    }
    return true;
}

private List<String> generateBoard(int[] queens, int n) {
    List<String> board = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        char[] row = new char[n];
        Arrays.fill(row, '.');
        row[queens[i]] = 'Q';
        board.add(new String(row));
    }
    return board;
}

}