[hermanschaaf]

It is indeed machine-solvable; I wrote a solver for regexcrossword.com puzzles a while back (https://github.com/hermanschaaf/regex-crossword-solver). It was great fun, maybe even more than solving the puzzles by hand!

[mtharrison]

Will your tool work on this puzzle though? I don't think so because it has backreferences.