Crossword generator

A couple months ago, someone asked me to create a set of custom crossword puzzles. Each puzzle was provided as a text file, with a word and a clue per line, and while there are lots of crossword generators online, none seemed to handle both plain-text input and the number of words per puzzle I needed. So I made another one. You can use it here.

The data model for a crossword is quite simple: a map of cell coordinates to characters. A handful of basic functions will find places a word can be added, check for invalid intersections or adjacencies, and add the word to the puzzle. When a word fits multiple locations, I tried picking one randomly, but that strategy had two drawbacks: 1) puzzles sometimes reached a configuration where a new word couldn't fit anywhere, and 2) puzzles usually spread out rather than staying compact.

To fix the first problem, I had to stop thinking in single solutions and instead think in multiples. For each word added to the puzzle, there are usually many places it can go, and rather than pick one early, I deferred making a choice and used all the possibilities. Then, for each possible puzzle, I added the possible locations for the next word. Naturally that created a combinatoric explosion, which became too slow by about twenty words, so after placing each word, I narrowed the options to just ten of the possibilities before continuing with the next word. That wouldn't guarantee generating a valid puzzle, but for the thirty-word puzzles I was trying to generate, I didn't have any trouble.

The second problem was easily solved after solving the first problem. Now that I was no longer working with a single puzzle but with many, I could choose how I prioritized them. When I narrowed the number of puzzles to just ten, I picked the ten most compact layouts, those whose width was closest to their height. I tried a couple other approaches, specifically minimizing the number of cells (i.e., maximizing the number of word intersections) and minimizing the number of empty spaces, but while both did produce less sprawling puzzles, they also tended to produce puzzles that were wide and short or tall and thin, and printing them on a single page would shrink the cells too small to write in. Square-ish proportions worked much better.

If you have suggestions for further improvements, please email me.