N-Queens

hard backtracking array

Problem

Place n queens on an n × n chessboard so that no two queens attack each other (no two share a row, a column, or a diagonal). Return all distinct solutions.

Walk row by row. For row r, try each column c; reject if c is already used by an earlier queen or any earlier queen sits on the same diagonal (r + c or r − c). On success, recurse; on failure, undo and try the next column.

Inputn = 4

Output2 solutions

def solve_n_queens(n):
    cols, pos, neg = set(), set(), set()
    board = [["."] * n for _ in range(n)]
    res = []
    def backtrack(r):
        if r == n:
            res.append(["".join(row) for row in board])
            return
        for c in range(n):
            if c in cols or (r + c) in pos or (r - c) in neg:
                continue
            cols.add(c); pos.add(r + c); neg.add(r - c)
            board[r][c] = "Q"
            backtrack(r + 1)
            cols.discard(c); pos.discard(r + c); neg.discard(r - c)
            board[r][c] = "."
    backtrack(0)
    return res

function solveNQueens(n) {
  const cols = new Set(), pos = new Set(), neg = new Set();
  const board = Array.from({ length: n }, () => Array(n).fill("."));
  const res = [];
  function backtrack(r) {
    if (r === n) { res.push(board.map((row) => row.join(""))); return; }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || pos.has(r + c) || neg.has(r - c)) continue;
      cols.add(c); pos.add(r + c); neg.add(r - c); board[r][c] = "Q";
      backtrack(r + 1);
      cols.delete(c); pos.delete(r + c); neg.delete(r - c); board[r][c] = ".";
    }
  }
  backtrack(0);
  return res;
}

class Solution {
    Set<Integer> cols = new HashSet<>(), pos = new HashSet<>(), neg = new HashSet<>();
    List<List<String>> res = new ArrayList<>();
    int n;
    char[][] board;
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(0);
        return res;
    }
    void backtrack(int r) {
        if (r == n) {
            List<String> sol = new ArrayList<>();
            for (char[] row : board) sol.add(new String(row));
            res.add(sol);
            return;
        }
        for (int c = 0; c < n; c++) {
            if (cols.contains(c) || pos.contains(r + c) || neg.contains(r - c)) continue;
            cols.add(c); pos.add(r + c); neg.add(r - c); board[r][c] = 'Q';
            backtrack(r + 1);
            cols.remove(c); pos.remove(r + c); neg.remove(r - c); board[r][c] = '.';
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    set<int> cols, pos, neg;
    vector<string> board(n, string(n, '.'));
    vector<vector<string>> res;
    function<void(int)> backtrack = [&](int r) {
        if (r == n) { res.push_back(board); return; }
        for (int c = 0; c < n; c++) {
            if (cols.count(c) || pos.count(r + c) || neg.count(r - c)) continue;
            cols.insert(c); pos.insert(r + c); neg.insert(r - c); board[r][c] = 'Q';
            backtrack(r + 1);
            cols.erase(c); pos.erase(r + c); neg.erase(r - c); board[r][c] = '.';
        }
    };
    backtrack(0);
    return res;
}

Explanation

The idea is to place queens one row at a time. Because each row gets exactly one queen, two queens can never share a row automatically — we only have to watch out for shared columns and diagonals.

We keep three sets for fast conflict checks: cols for used columns, pos for the "↗" diagonals (cells share r + c), and neg for the "↘" diagonals (cells share r - c). A column c in row r is safe only if none of c, r + c, or r - c is already in those sets.

When we place a queen we add its three keys to the sets and mark the board, then backtrack(r + 1) to solve the next row. If that branch dead-ends, we undo everything (discard the keys, reset the cell) and try the next column. Reaching r == n means a full valid board, which we copy into the results.

Example: for n = 4, the search discovers exactly 2 boards, such as columns [1, 3, 0, 2] read top to bottom.

The diagonal sets let each placement be validated in constant time, so the recursion quickly prunes bad rows and collects every solution.

Time: O(n!) worst case Space: O(n²)