[garaetjjte]

From quick glance it picks random matching word and goes with that, never reverting that decision. This allows only for generating rather low-density crosswords, where much of the board is empty.

Keeping a "stack" of crosswords, each one with one word added, iterating through possible words, and when nothing matches dropping "stack frame" and retrying with another word on previous level, would allow to generate much denser crosswords.

[tobr]

I wrote a crossword generator one or two years ago - it used this approach but for individual letters, not whole words. You’d feed it a pattern of blank squares. If I recall correctly, it used a dictionary to find all the words that would fit in each current row or column, and counted how many different possible letters each square could take. If it found a row or column with no matches, it would backtrack - otherwise it would take one of the squares with the fewest possible letters, fill one of them in, and recurse. If that would fail it would try the next possible letter in the list, until it ran out of letters, in which case it would also backtrack.

It made it possible to produce incredible dense crosswords, but it wasn’t very efficient, as it would retry certain impossible local solutions again and again and again. I wonder if it would be more or less efficient to do one whole word at a time, as you suggest.

[maynman]

That sounds pretty cool. I also found it difficult to optimize for both performance and word density with the approach I took. Maxing out on one seemed to negatively affect the other. I'm sure there have to be some better algorithms out there to do this sort of thing.