Generating symbol matrices that satisfy regular expressions row- and column-wise

I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one.

For example, say I have $N=3$, regular expression $c^ab^$ for rows and $b^ac^$ for columns. A solution would be

$\qquad\displaystyle\begin{pmatrix}
a & b & b \\
c & a & b \\
c & c & a
\end{pmatrix}$

I'm trying to find an algorithm that is faster than the brute force one. I am further looking for a way to split this algorithm in independent processes so I can use parallelism to decrease the time needed to reach a solution.

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.

StackExchange Computer Science Q#39917, answer score: 2