N-Queens

def solve_n_queens(n: int) -> list[list[str]]:
    result = []
    cols = set()
    diag = set()      # r - c
    anti_diag = set()  # r + c

    board = [['.' ] * n for _ in range(n)]

    def backtrack(row: int):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti_diag:
                continue
            cols.add(col)
            diag.add(row - col)
            anti_diag.add(row + col)
            board[row][col] = 'Q'
            backtrack(row + 1)
            board[row][col] = '.'
            cols.discard(col)
            diag.discard(row - col)
            anti_diag.discard(row + col)

    backtrack(0)
    return result

if __name__ == '__main__':
    solutions = solve_n_queens(4)
    for sol in solutions:
        for row in sol:
            print(row)
        print()
    # .Q..    ..Q.
    # ...Q    Q...
    # Q...    ...Q
    # ..Q.    .Q..

    print(f"4-queens solutions: {len(solutions)}")  # 2
    print(f"8-queens solutions: {len(solve_n_queens(8))}")  # 92