Over the years I have enjoyed solving crossword puzzles, but I did not fully appreciate the computational complexity of generating them.