48. N-Queens

Place exactly one queen per row. A column is safe if that column and both of its diagonals are unoccupied, checkable in O(1) with three sets.

One queen per row

Since no two queens can share a row, we place exactly one per row and only decide its column. Three sets make the safety test O(1):

• cols — occupied columns.
• diag — occupied row - col diagonals (↖↘ direction).
• anti — occupied row + col anti-diagonals (↗↙ direction).

Walk-through

backtrack(row):
    if row == n: record the board; return
    for col in [0, n):
        if col in cols or (row-col) in diag or (row+col) in anti: continue
        place queen; recurse(row+1); remove queen

When row == n, every row holds a safe queen — snapshot the board as a list of strings ("..Q." per row).

Worked example

n = 4 yields two solutions:

.Q..      ..Q.
...Q      Q...
Q...      ...Q
..Q.      .Q..

Complexity

• Time: O(n!) — the branching factor shrinks each row as columns/diagonals fill.
• Space: O(n) for the sets and recursion (excluding output).

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    private int n;
    private char[][] board;
    private Set<Integer> cols = new HashSet<>();
    private Set<Integer> diag = new HashSet<>();  // row - col
    private Set<Integer> anti = new HashSet<>();  // row + col
    private List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.board = new char[n][n];
        for (char[] row : board) java.util.Arrays.fill(row, '.');
        backtrack(0);
        return res;
    }

    private void backtrack(int row) {
        if (row == n) {
            List<String> config = new ArrayList<>();
            for (char[] r : board) config.add(new String(r));
            res.add(config);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.contains(col) || diag.contains(row - col) || anti.contains(row + col)) continue;
            cols.add(col);
            diag.add(row - col);
            anti.add(row + col);
            board[row][col] = 'Q';
            backtrack(row + 1);
            cols.remove(col);
            diag.remove(row - col);
            anti.remove(row + col);
            board[row][col] = '.';
        }
    }
}