Q79: N-Queens. - DSA Patterns (Multi-Lang)

In Simple Words: Place one queen per row. Track attack lines with three sets: cols, posDiag (r + c), and negDiag (r - c). If cell is safe, place queen and advance to row + 1.

Time: $O(N!)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def solveNQueens(n: int) -> list[list[str]]:
    col = set()
    pos_diag = set()  # (r + c)
    neg_diag = set()  # (r - c)
    res = []
    board = [["."] * n for _ in range(n)]

    def backtrack(r):
        if r == n:
            res.append(["".join(row) for row in board])
            return
        for c in range(n):
            if c in col or (r + c) in pos_diag or (r - c) in neg_diag:
                continue
            col.add(c); pos_diag.add(r + c); neg_diag.add(r - c)
            board[r][c] = "Q"
            backtrack(r + 1)
            col.remove(c); pos_diag.remove(r + c); neg_diag.remove(r - c)
            board[r][c] = "."

    backtrack(0)
    return res