def n_queens(n):
    output, columns = [], []
    used_cols, down, up = set(), set(), set()
    def visit(row):
        if row == n:
            output.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in columns])
            return
        for col in range(n):
            if col in used_cols or row - col in down or row + col in up:
                continue
            columns.append(col)
            used_cols.add(col)
            down.add(row - col)
            up.add(row + col)
            visit(row + 1)
            up.remove(row + col)
            down.remove(row - col)
            used_cols.remove(col)
            columns.pop()
    visit(0)
    return output