I had a lot of fun writing a program to solve this puzzle last year. I wrote about it here: http://almostobsolete.net/regex-crossword/part1.html

The Haskell code is also on GitHub