Building a Crossword Puzzle Generator with JavaScript (opens in new tab)

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.

I had fun making it. I'm glad you've found it valuable :)

I have a great story about generating word searches. I once got an angry email from a superintendent at a school district in Washington state using my algorithm. He said 'the generator inserted the phrase "killanigger" in the middle of the word search. This is obviously intentional on the part of the programmer since the odds of a phrase of this length being generated randomly is exceedingly small.'

I was very confused because I had implemented a bad word filter which I knew worked (it was the most interesting part of building a word search). And obviously, I didn't hard code that string in my program!

I asked to see the offending puzzle. Upon inspection, I found that the word search contained the word "ORIGINAL". When reversed for the word search it is "LANIGIRO" (which contains the substring "NIGIRO"). The start of another word - "LAW" - was placed next to "LANIGIRO" (by random chance) creating the string "LLANIGIRO". The two preceding randomly chosen letters were "K" and "I", forming the string "KILLANIGIRO".

I explained it to the superintendent, and all was well again.