A crossword layout is a two-dimensional grid that describes where the answers are located. These answers are to be placed in horizontal and vertical blocks of contiguous empty cells. The goal of this project is to develop an algorithm that takes in a crossword layout along with a word list and fills all such blocks with valid words. This is an essential task when constructing a crossword puzzle. Therefore, we call it the Crossword Puzzle Construction Problem (CPCP).
During summer of 2020 Otis Peterson worked with Professor Michael Wehar at Swarthmore College on solving the crossword puzzle construction problem. In particular, we implemented our own heuristic algorithms (based on established approaches) to provide a web-based crossword construction application. Otis presented this work at the National Conference on Undergraduate Research (NCUR 2021). See our accepted abstract and an explanation of our implementation @ crosswordconstruction.com
The code in this repo is a self-contained demonstration of our original implementation. You can simply use python to run the test_crossword.py file to test our algorithm on an example 5 by 5 crossword layout. Or, you can install flask and run the flask_app.py file. Then, you can navigate to the local host url in your web browser to generate crossword puzzles using our demonstration UI. Alternatively, you can try out our algorithm @ crosswordconstruction.com
We included a sample word list of 100,000 suggested English words. We encourage you to add your own word lists. You can simple create files wordlists/your_word_list.txt or wordlists/your_other_word_list.txt to test our implementation with your own word lists.
- MIT
- Michael Wehar
- Otis Peterson
- Our UI demo uses Bootstrap.