Java 实现 N 皇后问题回溯算法 - 简易代码示例

class Solution { public List<List> solveNQueens(int n) { List<List> res = new ArrayList<>(); int[] queens = new int[n]; Arrays.fill(queens, -1); // 初始化所有皇后的位置为-1 backtrack(res, queens, n, 0, new HashSet<>(), new HashSet<>(), new HashSet<>()); return res; }

private void backtrack(List<List<String>> res, int[] queens, int n, int row, Set<Integer> col, Set<Integer> diag1, Set<Integer> diag2) {
    if (row == n) {
        // 将皇后的位置转化为字符串形式，加入结果列表
        List<String> board = generateBoard(queens, n);
        res.add(board);
    } else {
        for (int i = 0; i < n; i++) {
            if (col.contains(i)) continue; // 列上有皇后，跳过
            int diagonal1 = row - i;
            if (diag1.contains(diagonal1)) continue; // 正对角线上有皇后，跳过
            int diagonal2 = row + i;
            if (diag2.contains(diagonal2)) continue; // 反对角线上有皇后，跳过
            queens[row] = i; // 在(row,i)放置皇后
            col.add(i); // 将列i加入列集合
            diag1.add(diagonal1); // 将正对角线(row-i)加入正对角线集合
            diag2.add(diagonal2); // 将反对角线(row+i)加入反对角线集合
            backtrack(res, queens, n, row + 1, col, diag1, diag2); // 继续往下一行放置皇后
            queens[row] = -1; // 回溯到上一行，将皇后位置重置为-1
            col.remove(i); // 将列i从列集合中移除
            diag1.remove(diagonal1); // 将正对角线(row-i)从正对角线集合中移除
            diag2.remove(diagonal2); // 将反对角线(row+i)从反对角线集合中移除
        }
    }
}

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;
}

}