We are given a $0$-$1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0$-$1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z}$) where $\mathbf{1}$ is the all $1$ vector. If there exists such a binary vector then we would like to compute all of them or at least comment on the total number.

Are there any theoretical results in this direction? If not, then can we compute this without going through all $2^n$ possibilities where $n$ is number of columns of $A$?

In full generality it seems to be an NP-complete problem as pointed out here: http://mathoverflow.net/a/97140/34180. So, assume that $A$ is the incidence matrix of a highly symmetrical incidence structure whose full automorphism group is known.

Edit: If the row sum is $r$ and column sum $s$ then this can be interpreted as finding perfect matchings in an $s$-uniform $r$-regular hypergraph. The smallest case I am interested in is a $5$-uniform $5$-regular linear hypergraph (at most one edge through every pair of vertices) which has $1365$ edges (and the same number of vertices).