Interior_Banner_Events

Automatic Crossword Generation

Otis Peterson, Michael Wehar, Department of Computer Science, Swarthmore College, 500 College Ave, Swarthmore, PA 19081

Algorithms Design is a field of study within computer science that is concerned with finding efficient algorithms that solve computational problems. There are many computational problems that we still do not know how to solve efficiently such as NP-hard problems. For our research project, we investigated computationally hard problems related to two dimensional word puzzles. In particular, we focused on the Crossword Construction Problem which is known to be NP-complete. Given a grid of shaded/empty cells and a wordlist, the Crossword Construction Problem asks if there exists a fill for the grid with letters such that every contiguous block of empty cells, horizontally and vertically, forms a word from the wordlist. In short, given a blank crossword grid, we are asking how to fill in every empty cell such that every across and down is a valid word. Crossword puzzles are regularly published in many leading newspapers and media outlets with millions of avid crossword puzzlers. As a result, Crossword puzzles are a well established puzzle with many common formats and rules. Although there are tools that assist with crossword puzzle construction, many crossword puzzle publishers still create crosswords by hand. Crossword puzzle publishers rely on submissions because there is still no accessible construction tool that is efficient and effective enough for publishers. For our project, we analyzed existing approaches for solving the crossword construction problem and implemented our own heuristic algorithms (based on established approaches) as part of a web-based crossword construction application. Although our algorithms theoretically run in exponential time, they are surprisingly efficient on real world examples. Going forward, we hope to make our crossword construction application publicly available, develop more performance metrics to compare our crossword construction algorithm with existing tools, and explore new algorithms to advance the field of automatic crossword puzzle construction.




Additional Abstract Information

Presenter: Otis Peterson

Institution: Swarthmore College

Type: Poster

Subject: Computer Science

Status: Approved


Time and Location

Session: Poster 5
Date/Time: Tue 12:30pm-1:30pm
Session Number: 4043