It's clearly in NP. One way to solve it is to order the squares in some order and combine all the NFAs in some nasty wreath product construction. Then we seek an accepting string. While this has an exponential state size blowup you may be able to construct lazily in the BFS and perhaps that keeps the complexity down.
Depends what you think N is doesn't it? What would be a variable parameter in this puzzle? The number of letters in the alphabet? The size of the regex expressions? The size of the board?
Nonograms are np-complete, so this type of puzzles is also np-complete.
Nope, it's basic regex so not NP-hard.
But it's a satisfiability problem. Seems NP-complete in the general case to me.
Huh yeah that could be right... I'll have to think about it more.