N-Queens

Problem

Distributed systems sometimes model resource allocation as a constraint satisfaction problem - no two tasks can share a CPU core, a memory bank, or a bus channel simultaneously. N-Queens is the canonical instance: place n queens on an n x n chessboard so no two queens share a row, column, or diagonal. Return all distinct solutions, each represented as a list of n strings where 'Q' marks a queen and '.' marks an empty cell.

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],
         ["..Q.","Q...","...Q",".Q.."]]
 
Input: n = 1
Output: [["Q"]]

Solution

Approach: Constraint-satisfaction backtracking, one queen per row, with three O(1) conflict sets.

Placing one queen per row by recursing row from 0 to n means two queens can never share a row by construction, so only three conflict types remain to check. Columns are tracked in cols. The two diagonal families collapse to arithmetic: every cell on a / (left) diagonal shares the same row - col, and every cell on a \ (right) diagonal shares the same row + col, so ld and rd hold those values. Before placing at (row, col) the code tests col in cols or (row - col) in ld or (row + col) in rd - if any set already contains the key, that square is attacked and the column is skipped. Otherwise it records queens[row] = col, adds the three keys, recurses to the next row, and on return removes exactly those three keys so sibling column choices start from a clean constraint state. Keeping a compact queens array (col per row) instead of a full board means each internal node does O(1) work; the O(n^2) board string is materialized only at a leaf, when row == n. The set lookups make every conflict check O(1) across all previously placed queens, not just the last one.

Edge cases: n = 1 places a lone queen and returns [["Q"]]. n = 2 and n = 3 have no valid placement, so the search exhausts and returns [].

Complexity: O(n!) time, O(n) space - branching shrinks each row as constraints prune columns; the recursion stack, queens array, and three sets are each at most length n (output excluded).