Crossword puzzles are supposed to be designed with a lot of white squares in clumps and with some sort of symmetry. There are different style traditions in the U.S., the U.K, and Japan. Sweden has a very strange looking puzzle style that is a bit different but having a lot of words overlap is common in all traditional puzzles.

File:CrosswordUSA.svg

U.S. Style Crossword Puzzle

Home grown crossword puzzles do not have those symmetry and clumping features. It is almost impossible for a normal person to create a puzzle for fun, and with a theme, and have it look like a traditional crossword puzzle. I found a shareware program that could generate traditional puzzles but the word list to do this would have to be enormous to find enough working overlaps to make it work for a given theme. Most people have a small set of words and so the traditional non-traditional puzzle style is used.

image

Non-Traditional Style Crossword Puzzle

The non traditional puzzle is just a collection of words that overlap at common letters. There is no pattern , not much overlap, and a lot of unused space between words.

I am creating a crossword puzzle for the puzzle race and I decided to try a few free crossword generator programs. First, I was surprised at how cool it was that a reasonable puzzle could be created in a few seconds. Then I was surprised by how easy it is to write a program to generate a crossword puzzle. Finally, I am not surprised that making a traditional puzzle is so hard.

Coding a Crossword Puzzle Generator

The code is quite simple although I did add some features that others did not seem to have.

First, the program makes an internal list of words. Then it picks one and stick it in the middle of the grid. The size of the grid is important because it might cause the puzzle to end up missing words if they can’t all fit. It also has the benefit of keeping the puzzle at or below a specific size if missing words is acceptable. Of course the size can be modified within certain limits. I use a larger fixed-size grid internally and use just a portion of it depending on the size selected by the user.

Next, the program makes a list of all of the places that a word might start. This is essentially each square in the entire grid but in a random order. The random order is what allows the puzzle to look different when created more than once. It then checks each location to see if a word can be placed there horizontally or vertically. The word must be placed on blank squares or squares that have a correct letter for the word. There are also rules about blank spaces next to letters and before and after the word.

image

Skipping Adjacency Rules

If letters are allowed to be placed on any blank square without regard to the squares next to it then the puzzle will just be wrong as can be seem in the above image.

When all locations in the puzzle and all words have been tried, the puzzle should be done. It is possible that there are left over words that just could not be placed in the puzzle. My code does not add them as separate words with no overlap to any others because this seems to defeat the purpose of a crossword puzzle.image

My Generated Puzzle

My puzzle generator follows the rules specified before but also generates large numbers of puzzles in order to find the “best” one possible. I define a good puzzle as one with many overlapping words. A worst-case puzzle would have two less overlaps than there are words in the puzzle. IN that case, the overlaps don’t help people solve the puzzle much since each word would have one or two overlapping letters and no more. I score my puzzles by counting overlaps and keep the best scoring puzzle when running the generator.

You can see in my generated puzzle in the image above that the word GENERALSTORE has five overlaps and that RULER, PLATE, TELEPHONE, and GENERALSTORE form a square, or a circular set of overlaps. This is good for helping people get letters for words that they are not sure about. These circular overlaps allow there to be more overlaps than words and also contribute to the puzzle being smaller in size than lesser scoring puzzles. If two puzzles have the same score then the smaller of the puzzles is the one kept. Smaller is also generally better just for aesthetic reasons. A puzzle should not be spread out on the page too much.

The one thing that my generator, and the free versions that I have tried on the web, all do not have is the ability to form clumps of letters. The first and easiest form of clump is where the starts of two words overlap the ends of two others.

image

Easy Clumping

I gave the image above the caption “Easy Clumping” because this is reasonably easy to do by hand. Unfortunately, it is not as easy to do by writing code. The code is not difficult to write but it does require stepping through every word then stepping through every remaining word, and so on, to get four words that have the right set of shared letters. Since there are four different ways to do this type of overlap, there are four pieces of code to do all of the testing of the words to see if they fit. Additionally, extra code is needed to check all four words at the same time to see if other rules are violated like if other words already in the puzzle block one or more of these new words.

I still plan on adding code to handle the four-way clump but it will be a lot more code in an otherwise simple program.

I also need to generate bitmap files with a blank version and an answer version of this puzzle and the blank version needs numbers for the across and down hints. After that, Maybe I’ll look at more complex overlap situations that I can handle to make the puzzle more compact and a little more like a traditional puzzle.

Dave