NYT Crossword Puzzle Constructor
Contribution:
Co-Authored this project. System architecture, domain analysis, consolidating English words for the dictionary.
I implemented the objects, classes, and methods that constructed and manipulated crossword data.
Description:
The goal of this project was to understand the best techniques for constraint satisfaction problems in the domain of the English language. More specifically, the goal was to discover whether there exist practical
applications for constraint satisfaction problems with the capabilities of generating a solved New York Times style crossword puzzle automatically. At a minimum it should be able to generate a crossword significantly
faster than an average person could by hand. Here are some solutions in plaintext, or viewed below.
The domain of the problem included all legal English words along with well known names, phrases, or abbreviations, similar to those one would expect to find in a traditional New York Times style crossword puzzle. A dictionary was created in order to house these words, names, and phrases comprising the domain.
A particular blank layout was used uniformly for all of the crosswords generated. This blank layout consisted of “58 slots” containing words, 29 amount of which were across slots and 29 amount of which were down
slots. Slots were identified by a “marker number” as well as a direction. For example, slots could be designated as the following: (3,across) where “3” is the marker number and “across” is the direction. Another
possible configuration is (3, down) in which the marker number is also “3”, however the direction in this case is “down”. Additionally, these two aforementioned slots are an ordered list of cells. (3,across) and (3,down)
both share the same cell– which represents the starting letter of these slots. In high quality crosswords, the general idea is to maximize the number of slots that intersect such that, for all slots, each cell is at an
intersection of two orthogonal slots. The problem is solved when all slots contain a valid English word.
The program runs a Backtracking search while utilizing the MRV heuristics. After the solution is partially complete, it uses LCV heuristic to reduce the redundancy of each search step. More information on techniques used can be found here.
Full source code on Github
