A Python script to generate crossword puzzles

I'am quite the fan of the little crossword books in the checkout isle. Looking at one, naturally the question occured to me on how these things are generated. After some googling you'll find that they are commonly generated by computers and there isn't an exact way to generate them. One of the reasons for that is that crossword puzzles can look quite different; compare the back of a cereal box to a newspaper for example. Density of words is a key difference you will generally find accross examples.

Taking then my thoughts and questions, I decided to make a program that generates the puzzles that I find confortably dense.

Words can only go down or accross, upward and reverse are confusing. Finding possible matches in of words is simple in it of itself. To get optimal density I went with a point system. Possible places to place a new word are assigned points given 4 criteria.

• Points are given if it intersects a word on a vowel.
• Points are given if it the intersection is closer to the middle of the word.
• Points are removed if the start location is crowded by other words.
• Points are removed if the end location is crowded by other words. Then it simply becomes a matter of picking the placement with the most points.

However, since the best placement for a word is constrained by the words allready placed on the grid this might not be the optimal solution. As is with any search problem we might be stuck in a local minima. To accomodate this we shuffle the word list and generate multiple grids. The grid with the highest number of total points is the chosen one.

Expects 4 Arguments:

1. Number of crossword grids to generate
2. Number of words in each puzzle
3. Max size of grid
4. Number of how many grids to test before picking one Example:

python ./GridWorld.py 2 20 40 3

Much credit to adambom for his dictionary respoitory found here. And of course to Project Gutenberg for putting up the webster dictionary in the first place.

Dictionary and Project Gutenburg have their licences. My code is under MIT.