This is a really cool idea! It seems really hard though, I tried for a while and didn't get far. Would be keen to see one that's a little easier, maybe with less * qualifiers and more + or ?
I tried this for over 20 minutes and made almost zero progress because I thought the expressions also had to be words, like a crossword puzzle. Oops. It might be worth clarifying that somewhere.
It seems impossible?
On the left a horizontal must start with F: F.[AO].[AO].*
However, the diagonal for that cell may not include an F (aside from the start): [^X]*(DN|TE|NI)
https://blog.nelhage.com/post/regex-crosswords-z3/ was posted a few days ago here and is an interesting way to solve these
For something a bit simpler I made redoku a while ago: https://padolsey.github.io/redoku/
Yesterday, I discovered regexle [1] and today found out that this was the inspiration for it.
I think I've seen this puzzle before, but I really enjoyed myself gradually solving it while doing other things in the last two hours. I'm sharing this for anyone else who wants a way to spend their afternoon!
[1]: https://regexle.com