N-Queens Problem

Problem Statement

Place N queens on an N×N chessboard such that no two queens attack each other. Return all possible board arrangements.

Example: Input: N = 4 → Output: [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]

Approach 1: Backtracking

Explanation: Place queens row by row, check safe positions, backtrack if stuck.

Time Complexity: O(N!)

Space Complexity: O(N²) (board storage)

function solve(row):
    if row == N:
        add board copy to result
        return
    for col in 0..N-1:
        if position (row,col) is safe:
            place queen
            solve(row+1)
            remove queen
solve(0)

Approach 2: Using Hash Sets for Safety

Explanation: Track occupied columns and diagonals using sets for faster checks.

Time Complexity: O(N!)

Space Complexity: O(N) (sets + recursion stack)

cols, diag1, diag2 = sets
function solve(row):
    if row == N:
        add board copy to result
        return
    for col in 0..N-1:
        if col not in cols and (row+col) not in diag1 and (row-col) not in diag2:
            place queen
            add col, row+col, row-col
            solve(row+1)
            remove queen and sets
solve(0)

Approach 3: Bitmask Optimization

Explanation: Use bitmasks to track columns and diagonals for N ≤ 32 efficiently.

Time Complexity: O(N!)

Space Complexity: O(N) (recursion stack)

function solve(row, cols, diag1, diag2):
    if row == N:
        add solution
        return
    available = ~(cols | diag1 | diag2) & ((1<>1)
solve(0,0,0,0)