I have the following #P-complete problem:
Given an alphabet $\Sigma$ and a matrix $M$ where each entry can be a symbol from $\Sigma$ or the wildcard symbol $*$, find the number of strings $s$ with the property that there exists $i$ such that for all $j$, $M_{i,j} \neq *$ implies $s_j = M_{i,j}$.
Example: If $\Sigma = \{a,b,c\}$ and $M$ = $$\left(\begin{matrix} a&*&b \\ *&c&* \end{matrix} \right)$$ then there are three satisfying strings: $aab,abb,acb$.
I was told this can be solved using BDDs, somehow, such that a lot of caching is possible. How does that work? Also, what are other algorithms for this?
Proof of #P-completeness: We reduce from #UNSAT, the problem of counting the number of unsatisfying assignments for a boolean formula. Given a formula $\varphi$ with $n$ variables and $m$ clauses, make an $m$ by $n$ matrix $M$ over the alphabet $\Sigma = \{0,1\}$ such that $$M_{i,j} = \begin{cases} 1\text{ if the $j^{th}$ literal is unnegated in the $i^{th}$ clause,} \\ 0\text{ if the $j^{th}$ literal is negated in the $i^{th}$ clause,} \\ *\text{ otherwise.} \end{cases} $$ Then the number of strings with the above property equals the number of unsatisfying assignments for $\varphi$.