Image of Generated Crossword Puzzle (source https://www.crosswordconstruction.com)
Introduction: Crossword puzzles
In this article we explore crossword puzzle construction. Furthermore, we show how techniques from AI can be used to solve the crossword construction problem.
I love words, language, and puzzles. But, to be honest, I am not very good at solving crosswords. Because I struggle with solving crosswords, I felt like constructing a crossword was an unobtainable goal for me. But then, I met a talented student named Otis Peterson who has been solving crosswords since he was a kid. He was even working on constructing his own crossword puzzle too.
The more we talked together about crosswords, the more convinced we were that we could build our own application for crossword construction. So with the support of Swarthmore College, we were able to pursue a research project to build a crossword construction web application at https://www.crosswordconstruction.com.
Before, we discuss our web application, we need to tell you a bit more about crosswords and the concept of computational hardness.
Crosswords are fun and educational word puzzles that are commonly found in newspapers, media, websites, and mobile apps. A crossword takes the form of a grid containing empty and shaded squares along with a list of clues. The empty squares are meant to be filled in with alphabet characters to form horizontal and vertical answers that match the given clues.
There are many common restrictions that are applied to crosswords. For example, some publishers require crosswords to have 180-degree symmetry and for all answers to be at least 3 characters in length. Such restrictions can make the crosswords more dense with answers and more challenging to construct.
Now, we can define the Crossword Construction Problem. This problem asks for a filling to a given crossword grid so that every horizontal and vertical answer is a valid word within a given dictionary.
For this problem, we do not generate the clues. Generating clues is a separate and important problem that we have not yet pursued.
In general, crossword construction is considered to be a challenging computational problem. In particular, the crossword construction problem is NP-complete.
NP-completeness is an important mathematical property in Computer Science. From a practical point of view, NP-complete problems are widely considered to be computationally hard. In other words, we do not yet know if there are efficient algorithms that solve these problems in all cases.
For more information about the crossword construction problem and NP-completeness, we refer the reader to GP14 in Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David Johnson.
Although the crossword construction problem is NP-complete, we think that heuristics can be used to solve the problem efficiently for small grid sizes and large dictionaries. A naive approach for solving the crossword construction problem is to try all combinations of filling in the grid with potential answers from the dictionary. However, this approach can be greatly improved if we can reduce the number of combinations that we have to try from the dictionary at each step. In fact, some interesting concepts and techniques for doing so were introduced in the paper Search Lessons Learned from Crossword Puzzles which was published in AAAI 1990 by M. Ginsberg, M. Frank, M. Halpin, and M. Torrance.
For our solution, we applied related techniques to continually reduce the number of combinations as efficiently as possible. In the end, our algorithm was successful and it consistently generated standard sized crosswords (15 by 15) on large word lists containing 100,000’s of words. A prototype of our web application with an early implementation of our algorithm can be found at https://www.crosswordconstruction.com/generator.
We consider our algorithm to be related to AI because our algorithm essentially prunes a search tree at every step which is a technique found within AI related algorithms for search, decision making, and games.
Prior Work on Crosswords
Sometimes less restrictive crosswords appear in elementary school classrooms. These puzzles have fewer limitations and contain fewer horizontal and vertical answers. We refer to such puzzles as classroom crosswords.
I previously worked with Itay Livni and several collaborators to construct classroom crosswords. Our work titled Converting unstructured web data into sequenced STEM educational games was presented at PyCon 2018.
At that time, I designed and implemented a classroom crossword layout generator. This program would take in a list of words and generate a classroom crossword puzzle with these words as horizontal and vertical answers. In particular, the program would attempt to generate a layout by trying to maximize the number of connections between answers while balancing the puzzle’s height and width. This specific component of our broader work was released open source and can be found at https://github.com/MichaelWehar/Crossword-Layout-Generator.
Thank you very much for reading! We gladly welcome any thoughts, feedback, or comments.
I had a really great time working with Otis and he did an amazing job! I hope that we can continue to advance our crossword construction algorithms to produce better quality puzzles that are fun and challenging to solve.