Solving a crossword puzzle the hard way
3:10pm - 3:35pm on Saturday, October 7 in MadisonAlec Barrett
- Audience Level:
- All
- Slides:
- https://github.com/anbnyc/xword/blob/master/PyGothamTalk.ipynb
- Watch:
- https://youtu.be/tT9VL-PPlis
Overview
I set out to write a program that can solve the New York Times crossword through natural language processing. Using the Natural Language Toolkit (NLTK) and spaCy, my program parses the clues, generates a set of candidate answers, then narrows them down based on word length and intersecting letters.
Description
The New York Times crossword puzzle gets harder as the week goes on. I can confidently finish a Thursday, but struggle a little on Friday and Saturday. In an effort to become a better solver, and a better programmer, I set out to solve a crossword puzzle the hard way: by writing a Python program to do it for me.
The task is not trivial, and I have not previously come across automated crossword puzzle solvers in the wild. Crosswords are rife with wordplay and non-linear thinking, which still elude contemporary AI. The computer’s advantages are speed and breadth: it can rapidly filter lists of words based on surrounding words and related criteria, and I allow my program access to libraries that serve as dictionary, thesaurus, and search engine. My program parses the clues and feeds them into Natural Language Toolkit (NLTK), spaCy, Google Knowledge Graph, and Wikipedia. From the responses, it generates a set of candidate answers, then narrows them down based on word length and intersecting letters.
In this talk I will explain the program’s pipeline – from inputting a series of clues and grid to producing a list of candidate answers ranked by how likely they are to be correct. There will be a live demonstration of the program using the NYT’s most recent Monday puzzle.