Angry Words: An Automated Crossword Solver

The goal of Angry Words was to solve crossword puzzles using a computer. Given an empty grid and a list of clues, we tried to generate the most accurate possible fill of the puzzle. We used techniques in artificial intelligence, natural language processing, and other areas of computer science to parse the clues, come up with possible answers, and ultimately solve the puzzle. We designed our project around three main components: the solvers, the decider, and the resolver. The solvers\u27 job was to interpret the clues and suggest potential answers. Each solver was tied to a specific knowledge domain, such as Wikipedia or IMDB, from which it drew its information. The solvers would then propose their best guesses to the next component, the decider. The decider was in charge of selecting the best answers from those suggested by the solvers and use them to fill in the puzzle grid as well as possible. After the decider had come up with its best guess, there would often be some blank spaces left in the grid. The resolver\u27s job was to make final guesses as to what those letters should be. It intelligently filled in letters based on the current fill in both the down and across directions. Once all the gaps were filled in, the grid would be presented as our program\u27s best guess at a solution. Solving crosswords with a computer is a hard problem, but we managed to get pretty decent results. We were largely successful on crosswords early in the week. This was due to the fact that these crosswords tended to have fewer theme- or pun-based clues, and tended to reuse previously seen clues. For Monday puzzles, we could typically expect to fill in at least 90% of the letters correctly. Later in the week, when puzzles got harder, our performance decreased. We still tended to exceed 50% accuracy even on the harder puzzles, however. For more information, check out http://cs.carleton.edu/cs_comps/1213/crossword/final_results/index.htm