Case Study: Crossword Puzzle Constructor

       I had written a program to generate crossword puzzles, and I was seeking a market for the resulting puzzles. One publishing company indicated that it would accept my puzzles, but offered a very low price for each puzzle. The only way to produce a worthwhile amount of revenue was to generate bulk quantities of puzzles and sell them in large lots.

       The general-purpose crossword constructor that I had written was too slow for this. To obtain the speed I wanted, I decided to select a single puzzle diagram and write a program that would generate puzzles with that specific layout. Writing this program was slow and tedious.

       The general-purpose crossword puzzle constructor works by placing a single word at a time. It scans the space where the word belongs to find the word length and any letters that have already been placed. It then searches its word lists for matching words. After it places each candidate word, it scans to each side to see if there are any letters placed in the crossing word. Then it checks if there are any words that match these existing letters plus the letter from the new word. If not, the candidate word is rejected.

       The new program would take advantage of the fixed diagram. As each word is chosen, the program will know the length of the word, the positions where existing letters would be, and the positions of all known letters in the crossing words. There will be separate arrays giving all the valid combinations of 2 and 3 letters in words of each length, so the tests for valid crossing words can be done by a single lookup. For example, the array t6p235 would tell whether a given combination of letters occurs in positions 2, 3 and 5 in any 6-letter words. Thus t6p235[ord('L'),ord('P'),ord('C')] would be true because the word ALPACA has the letters LPC in positions 2, 3 and 5.

       All of this is simple in principle, but very lengthy to program and debug. In just a little 15x15 crossword puzzle layout there about 40 words in each direction containing about 195 letters. This means there are about 80 word searches to write and 190 tests for valid letters. There are also more than 50 letter-combination arrays to generate. Much of this can be done by copying the routines and editing them for each new word, but this is tedious, and difficult to get 100% correct.

       The Pascal Macro Compiler can eliminate all of the repetitious work. The macro program makes two passes through the puzzle. On the first pass, the macro program marks each square where a new letter is placed in each word. Then it scans to the side to see what letters had already been placed in each crossing word. The macro program keeps a table of each such combination of letters. At the end of this exploratory pass, the macro program generates a Pascal procedure to build an array for each unique combination of word length and letter positions.

       On the second pass, the macro program again marks each square where a new letter is placed in each word. This time, it generates the code to search for words fitting the existing letters, and the code to test the crossing words, using the arrays that have been built.

       Those are the main operations. The macro program also generates declarations for the arrays and other variables, generates the ends of FOR loops, generates code to set and test flags so a word does not get used twice, and generates some standard code to read the dictionary files and print the resulting puzzle.

       The only part of the process that the macro program does not perform is choosing the order for placing the words. I choose the order myself, and specify it in an integer array in the macro program.

       One great work-saver is that much of the macro code can be created from the Pascal code in my original general-purpose crossword puzzle constructor. An advantage of this approach is that the same macro program can generate crossword programs for any other puzzle layout I may want later.

       A crossword puzzle constructor generated by this approach is more than 100 times faster that using the general-purpose crossword constructor.

© Copyright 2005 Frank Rubin