I’ve been doing crosswords (American style) for most of my life but one thing I’ve never understood is how one goes about constructing them. It really is a hard problem when you think about it. Forget about clues and all that. Even forget about generating the grid. How do you go about laying down words so that you get valid words both across and down?
A useful strategy for most Irreal readers is to change the question slightly to, “how would I generate a crossword with a program?” The answer is probably going to differ from what traditional constructors have done but at least it leads us to a solution.
Bill Moorier has long considered this problem and has a post that gives an overview. The TL;DR is that once he has a grid and a list of words and clues, he uses a backtracking search to fill in the grid.
Moorier’s post outlines a complete solution that includes generating the grid, filling in the words, and, with some post processing, fixing things like using the target word in the clue. I’m not so interested in that as in simply generating a filled in grid. Making up the clues is more of an art form as evidenced by the fact professional constructors generally rely on editors to provide—or at least tweak—the clues. I don’t know how good I’d be with that but I least I understand it.
The post doesn’t provide code or even a detailed algorithm for solving the problem but it does suggest some ways to proceed. If you’re interested in crossword construction, take a look at the post. It’s a short read and worthwhile for those with even a passing interest.