3 ms·

Is the complexity basically NP-hard, equivalent to a SAT solver or even harder?

• ladberg 6y ago
  Nope, it's basic regex so not NP-hard.
  • teawrecks 6y ago
    But it's a satisfiability problem. Seems NP-complete in the general case to me.
    • ladberg 6y ago
      Huh yeah that could be right... I'll have to think about it more.
• dandanua 6y ago
  Nonograms are np-complete, so this type of puzzles is also np-complete.
• wbl 6y ago
  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.
• cammil 6y ago
  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?