Finding number not in list with wildcards
Reduce from SAT. Consider a CNF formula $\phi = C_1 \land C_2 \land \ldots \land C_m$ over a set of variables $\{x_i\}_{i=1}^n$. Construct an instance of your problem as follows:

For each clause $C_i$, create a row (i.e. binary string) $B_i = b_1 b_2 \ldots b_n$, where 

$$ b_k = \begin{cases}
1 &amp; \text{if }\overline x_k \in C_i \\
0 &amp; \text{if } x_k \in C_i \\
* &amp; \text{if } x_k, \overline x_k \notin C_i
\end{cases}$$

We can preprocess $\phi$ to remove any clauses that contain both a literal and its negation, as these will of course always be satisfied and do not affect the result.

Any binary string $S$ that solves your problem also yields a satisfying assignment to $\phi$, using the reduction that sets  $x_i$ to the value of $S_i$.

Thus your problem is $NP$-hard. Since it is also clearly in $NP$, it is also $NP$-complete.