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 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.

Why not just use a random probabilistic approach to start with. Start with a word, and then repeatedly pick a random word and try to fit it into the current state of the puzzle without breaking the constraints on the size etc.. If you fail, just start all over again.

You will be surprised how often a Monte Carlo approach like this works.

I'd generate two numbers: Length and Scrabble score. Assume that a low Scrabble score means it's easier to join on (low scores = lots of common letters). Sort the list by length descending and Scrabble score ascending.

Next, just go down the list. If the word doesn't cross with an existing word (check against each word by their length and Scrabble score, respectively), then put it into the queue, and check the next word.

Rinse and repeat, and this should generate a crossword.

Of course, I'm pretty sure that this is O(n!) and it's not guaranteed to complete the crossword for you, but perhaps somebody can improve it.

This one appears as a project in the AI CS50 course from Harvard. The idea is to formulate the crossword generation problem as a constraint satisfaction problem and solve it with backtracking with different heuristics to reduce the search space.

To start with we need couple of input files:

1. The structure of the crossword puzzle (which looks like the following one, e.g., where the '#' represents the characters not to be filled with and '_' represents the characters to be filled with)

`

###_####_#
____####_#
_##_#_____
_##_#_##_#
______####
#_###_####
#_##______
#_###_##_#
_____###_#
#_######_#
##_______#    

`

2. An input vocabulary (word list / dictionary) from which the candidate words will be chosen (like the one shown follows).

   a abandon ability able abortion about above abroad absence absolute absolutely ...

Now the CSP is defined and to be solved as follows:

1. Variables are defined to have values (i.e., their domains) from the list of words (vocabulary) provided as input.
2. Each variable gets represented by a 3 tuple: (grid_coordinate, direction, length) where the coordinate represents the start of the corresponding word, direction can be either of horizontal or vertical and the length is defined as the length of the word the variable will be assigned to.
3. The constraints are defined by the structure input provided: for example, if a horizontal and a vertical variable has a common character, it will represented as an overlap (arc) constraint.
4. Now, the node consistency and AC3 arc consistency algorithms can be used to reduce the domains.
5. Then backtracking to obtain a solution (if one exists) to the CSP with MRV (minimum remaining value), degree etc. heuristics can be used to select the next unassigned variable and heuristics like LCV (least constraining value) can be used for domain-ordering, to make the search algorithm faster.

The following shows the output that was obtained using an implementation of the CSP solving algorithm:

`
███S████D█
MUCH████E█
E██A█AGENT
S██R█N██Y█
SUPPLY████
█N███O████
█I██INSIDE
█Q███E██A█
SUGAR███N█
█E██████C█
██OFFENSE█

`

The following animation shows the backtracking steps:

Here is another one with a Bangla (Bengali) language word-list:

I would get an index of each letter used by each word to know possible crosses. Then I would choose the largest word and use it as base. Select the next large one and cross it. Rinse and repeat. It's probably an NP problem.

Another idea is creating a genetic algorithm where the strength metric is how many words you can put in the grid.

The hard part I find is when to know a certain list cannot possibly be crossed.