[eutectic]

This problem is NP-hard by reduction from SAT. Treat each column as a truth variable and use the rows to encode CNF clauses. For example, `(A | ^C)` becomes `(1..)|(..0)`. Then set all the column regexes to `( 0* )|( 1* )` to enforce a consistent truth value for each variable.

[jonahx]

Could you elaborate on the encoding? What are valid mappings?

[eutectic]

A variable becomes '1' in the corresponding position and '.' everywhere else, and similarly with negations of variables and '0'. The regex is then just an alternation of these sub-regexes. This incurs just a linear blow-up in the number of variables, for the '.'s.

For an n x m grid, you can encode any CNF formula with n clauses on m variables. See here if you are unfamiliar with CNF: https://en.wikipedia.org/wiki/Conjunctive_normal_form