Ah, this brings me back. I remember coming across these a few years ago and spending a ton of time solving them. I wound up taking a crack at writing a regex cr

Ah, this brings me back. I remember coming across these a few years ago and spending a ton of time solving them. I wound up taking a crack at writing a regex crossword solver. Suprisingly a solver that used basic constraint satisifcation[0] was enough to solve every problem I threw at it. The core idea was for each cell, keep track of a list of possible letters that can go there. Initially you start with the full alphabet, and as the solver repeatedly narrows down the list for each cell as it gets closer and closer to completion. To hone in on the solution, the solver would iterate through each regex and see what characters could go in that row or column to match the regex. For example if you have the regex "(a|b)" against an cell, you can constrain the list of possible values to the cell to just the letters "a" and "b". For a slightly more complex example, if you are matching a regex "(abc|def)", and you know the middle character has to be an "a" or a "b", you know the string in that row or column is "abc". By repeatedly checking each regex, the solver gets closer and closer to the solution until it eventually solves it. Of course there's a chance the solver will get stuck. As a last resort, you can always resort to backtracking. I wound up finding implementing backtracking wasn't necessary since the approach I mentioned above was enough to solve every puzzle I threw at the solver. [0] https://en.wikipedia.org/wiki/Constraint_satisfaction_problem https://en.wikipedia.org/wiki/Constraint_satisfaction_proble...