N Nữ hoàng

def solve_n_queens_opt(n: int) -> list[list[str]]:
    col = set()
    posDiag = set()
    negDiag = set()
    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 posDiag or (r - c) in negDiag:
                continue
            col.add(c)
            posDiag.add(r + c)
            negDiag.add(r - c)
            board[r][c] = "Q"
            backtrack(r + 1)
            col.remove(c)
            posDiag.remove(r + c)
            negDiag.remove(r - c)
            board[r][c] = "."
    backtrack(0)
    return res

def solve_n_queens_brute(n: int) -> list[list[str]]:
    res = []
    board = [["."] * n for _ in range(n)]
    def is_safe(r, c):
        for i in range(r):
            if board[i][c] == 'Q': return False
            for j in range(n):
                if board[i][j] == 'Q' and abs(i-r) == abs(j-c): return False
        return True
    def backtrack(r):
        if r == n:
            res.append(["".join(row) for row in board])
            return
        for c in range(n):
            if is_safe(r, c):
                board[r][c] = "Q"
                backtrack(r + 1)
                board[r][c] = "."
    backtrack(0)
    return res