Generating symbol matrices that satisfy regular expressions row- and column-wise
Here's one idea that may still take exponential time in $N$ but is polynomial in the (length of) the regular expressions.

Consider strings over the shared alphabet $\Sigma$ of length $N^2$; each such string represents an $N \times N$ matrix stored row-wise. We insert a separation character $\$ \not\in \Sigma$ between rows.

We will now construct a finite automaton the accepts exactly the set of such strings that fulfill your two regular expressions.

Let $r$ resp. $c$ be the row resp. column regular expression


Clearly, $r_N = (r \cap \Sigma^N\$)^{N-1}(r \cap \Sigma^N)$ matches all matrices that match $r$ in every row. Transform $r_N$ into an NFA $A_{r,N}$.
Denote with $A^{(i)}_{c,N}$ the automaton that matches only every $N$-th 
input symbol (ignoring $\$$) against $c$, starting with the $i$-th. 
I will leave the construction as an exercise; suffice to say that we 
need at most $N$ copies of $A_c$.

Now, $A_{c,N} = A^{(1)}_{c,N} \cap \dots A^{(N)}_{c,N}$ accepts the set of all matrices each column of which matches $c$.
The automaton $A_{r,c,N} = A_{r,N} \cap A_{c,N}$ accepts all the matrices 
you want.
A simple graph traversal finds an accepting path in $A_{r,c,N}$ finds 
a solution matrix, if any.


The blowup in size is mild (i.e. at most a factor $N^2$) for all constructions but the intersections; these multiply sizes, so we may look at a factor $2^N$ for automaton size.

That's still way better than checking all $\Sigma^{N^2}$ possible matrices.