Even though it is NP-complete, you can do a lot better than searching through all $2^n$ possibilities. In practice, you might try a SAT solver, with the clauses
$\bigvee_{j: A_{ij} = 1} x_j$ for each row $i$ and $\overline{x_j} \vee \overline{x_k}$ for each pair $(j,k)$ such that for some row $i$, $A_{ij} = 1$ and $A_{ik} = 1$.
This can sometimes solve a problem with hundreds of clauses and variables
in a reasonable time.
Counting or estimating the number of solutions (in a case where that number is not $0$) might be more difficult.