Algorithm to generate a crossword

I came up with a solution which probably isn't the most efficient, but it works well enough. Basically:

1. Sort all the words by length, descending.
2. Take the first word and place it on the board.
3. Take the next word.
4. Search through all the words that are already on the board and see if there are any possible intersections (any common letters) with this word.
5. If there is a possible location for this word, loop through all the words that are on the board and check to see if the new word interferes.
6. If this word doesn't break the board, then place it there and go to step 3, otherwise, continue searching for a place (step 4).
7. Continue this loop until all the words are either placed or unable to be placed.

This makes a working, yet often quite poor crossword. There were a number of alterations I made to the basic recipe above to come up with a better result.

• At the end of generating a crossword, give it a score based on how many of the words were placed (the more the better), how large the board is (the smaller the better), and the ratio between height and width (the closer to 1 the better). Generate a number of crosswords and then compare their scores and choose the best one.
  • Instead of running an arbitrary number of iterations, I've decided to create as many crosswords as possible in an arbitrary amount of time. If you only have a small word list, then you'll get dozens of possible crosswords in 5 seconds. A larger crossword might only be chosen from 5-6 possibilities.
• When placing a new word, instead of placing it immediately upon finding an acceptable location, give that word location a score based on how much it increases the size of the grid and how many intersections there are (ideally you'd want each word to be crossed by 2-3 other words). Keep track of all the positions and their scores and then choose the best one.

I just recently wrote my own in Python. You can find it here: http://bryanhelmig.com/python-crossword-puzzle-generator/. It doesn't create the dense NYT style crosswords, but the style of crosswords you might find in a child's puzzle book.

Unlike a few algorithms I found out there that implemented a random brute-force method of placing words like a few have suggested, I tried to implement a slightly smarter brute-force approach at word placement. Here's my process:

1. Create a grid of whatever size and a list of words.
2. Shuffle the word list, and then sort the words by longest to shortest.
3. Place the first and longest word at the upper left most position, 1,1 (vertical or horizontal).
4. Move onto next word, loop over each letter in the word and each cell in the grid looking for letter to letter matches.
5. When a match is found, simply add that position to a suggested coordinate list for that word.
6. Loop over the suggested coordinate list and "score" the word placement based on how many other words it crosses. Scores of 0 indicate either bad placement (adjacent to existing words) or that there were no word crosses.
7. Back to step #4 until word list is exhausted. Optional second pass.
8. We should now have a crossword, but the quality can be hit or miss due to some of the random placements. So, we buffer this crossword and go back to step #2. If the next crossword has more words placed on the board, it replaces the crossword in the buffer. This is time limited (find the best crossword in x seconds).

By the end, you have a decent crossword puzzle or word search puzzle, since they are about the same. It tends to run rather well, but let me know if you have any suggestions on improvement. Bigger grids run exponentially slower; bigger word lists linearly. Bigger word lists also have a much higher chance at better word placement numbers.

I actually wrote a crossword generation program about ten years ago (it was cryptic but the same rules would apply for normal crosswords).

It had a list of words (and associated clues) stored in a file sorted by descending usage to date (so that lesser-used words were at the top of the file). A template, basically a bit-mask representing the black and free squares, was chosen randomly from a pool that was provided by the client.

Then, for each non-complete word in the puzzle (basically find the first blank square and see if the one to the right (across-word) or the one underneath (down-word) is also blank), a search was done of the file looking for the first word that fitted, taking into account the letters already in that word. If there was no word that could fit, you just marked the whole word as incomplete and moved on.

At the end would be some uncompleted words which the compiler would have to fill in (and add the word and a clue to the file if desired). If they couldn't come up with any ideas, they could edit the crossword manually to change constraints or just ask for a total re-generation.

Once the word/clue file got up to a certain size (and it was adding 50-100 clues a day for this client), there was rarely a case of more than two or three manual fix ups that had to be done for each crossword.