Crossword puzzles are a beguiling way of spending leisure time. For a small group of people, the professional crossword compilers who devise the puzzles, they are also a source of income. For an even smaller group of people, the process of devising crossword puzzles is an area for the application of computers. The main problems in this process are first, drawing up a crossword grid; second, finding an arrangement of words to fit the grid; and third, writing clues whose solutions give the words. Some success has been achieved in automating solutions to the first two problems, with crossword compiler programs that produce grids and word arrangements. These programs are not yet able to compete commercially with human crossword compilers, however. As for the third problem, the current state of the art does not include automatic techniques to devise the cryptic clues that are essential for harder puzzles.

This paper aims to provide a way of comparing the efficiency of crossword compiler programs. The authors propose a standard input and a standard execution environment for such programs so that execution times can be meaningfully compared. The standard input consists of a fixed 5 by 5 grid of squares for the puzzle format together with a fixed lexicon of 134 words from which the grid is to be filled. The standard execution environment uses an IBM/PC as the host system and includes additional constraints such as no use of disk storage and holding operating system overhead constant. The amount of time taken by different crossword compiler programs to produce a puzzle under these conditions can be compared more meaningfully than when different grids, lexicons, and host systems are used. The execution times of the programs are the only aspect of efficiency considered; space requirements are not mentioned.

The emphasis is on measuring the performance of the algorithm rather than of the compiler, so the input is designed to avoid measuring time spent in memory management and backtracking. This emphasis is a limitation of the approach used in the paper; internal memory is one of the resources most relevant to efficient performance. A standard approach to analyzing performance of algorithms, which avoids the problems of quantitative performance measurement, uses the O-notation to describe the complexity of algorithms; the authors do not mention this approach. Despite these limitations, the proposed standard and the execution times given for a crossword compiler program written by the authors will interest anyone involved in automating the process of compiling crosswords.