Well done. I don't know what you think but I found that most of the time the character classes would intersect perfectly (i.e. there'd only be one character possible once you intersect both sides of a single square). That made it pretty easy overall since for the vast majority of the board you don't have to worry about the "context".

But I guess if it's meant for an audience of folks not very familiar with regexes it's difficult enough as it is.

Well, thanks. I tried to cheat with https://github.com/blukat29/regex-crossword-solver and got hit with lex parsing errors! My limited python and 5 minute effort resulted in failure! At least I got to read the message though :-)

I'm assuming the solution isn't unique because I found some positions that are under-constrained.

Ah, but you have underscores where there should be spaces! ;)