Right now, it works using a logic programming engine (core.logic, essentially miniKanren), generating a bunch of strings that match the regex, and then applying them as constraints.
If I were to improve it, I'd parse the regex, walk the parse tree, and assign constraints that way. (There's already a regex parser in there: that's how the string generation works.) That was my first thought, but that's more complex than what I want to tackle before work :)
Right now there's a bug where if e.g. a regex AB|CD will get applied character-wise, so it might erroneously try AC or BD. The way to fix that is to make sure the answers actually match the regex all the way at the end.
Using a constraint engine has the cool feature that it can show you multiple answers if they exist. (That's not true for my current implementation, because the string generation is randomized, so there's no guarantee it will visit each possible string.)
Someone else has pointed out that there are a lot of clues in the titles, e.g. that the answers are palindromes. That would be easy to add:
(map (fn [vars] (l/== vars (reverse vars))) (concat rows cols))