N Queens - Java

public class NQueens {
    private int[] queens; // 用于存储每一行皇后的列位置
    private List<List<String>> solutions; // 存储所有解决方案

    public List<List<String>> solveNQueens(int n) {
        queens = new int[n];
        solutions = new ArrayList<>();
        backtrack(0, n);
        return solutions;
    }

    private void backtrack(int row, int n) {
        if (row == n) {
            // 找到一个解决方案，将皇后位置转换为字符串表示
            List<String> solution = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (queens[i] == j) {
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }
                }
                solution.add(sb.toString());
            }
            solutions.add(solution);
        } else {
            for (int col = 0; col < n; col++) {
                if (isValid(row, col)) {
                    queens[row] = col;
                    backtrack(row + 1, n);
                }
            }
        }
    }

    private boolean isValid(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;
    }
}