Project
Overview
Workflow
- .puz file is parsed and put into data structure
- Puzzle is passed to the decider
- Decider queries the solvers to generate guesses for all clues
- Solvers return their answers with associated confidences
- Decider combines the solvers' results to get full list of guesses
- Decider attempts to find the best solution to the puzzle
- Resolver fills in any blanks left in the decider's solution
- Final solution is returned to be displayed in the GUI or printed to console
Solvers
The solvers are what actually attempt to solve each clue, and they are responsible for accessing the data sets. Each solver has a method solve(String clue, int answerLength) that takes a string representing the clue and an int representing the number of letters in the answer. It then returns the solver's confidence in itself and a list of its suggested answers. This answer list is a list of tuples (word, confidence) representing each possible answer and the associated confidence for that word. The confidences summed across the entire list of tuples equals one.
Decider
The decider is the main logic which decides how to fill in the puzzle using the results from the solvers. To solve the puzzle it first queries the solvers on each clue. Then, for each clue, the decider:
- truncates answer lists for some solvers that return too many possibilities
- adjusts the answer confidences based on which solver suggested it
- combines confidences for answers that were suggested multiple times
After the answers are ranked, it begins trying to solve the puzzle. There are two different decider algorithms: a naive one which tries the highest confidence answers first and employs simple backtracking, and a more complex one that tries to solve different regions of the puzzle as well as possible and then combine the best fills.
Resolver
The resolver tries to intelligently fill any blanks in the puzzle left over after the decider terminates. It uses an ngram model built from past crossword data to generate the most likely column fills for the current puzzle. Although unlikely to get many letters correct, it helps the final output look complete by eliminating blanks in a slightly more intelligent way than randomly putting in letters.
Results
We're largely successful on crosswords early in the week. This is due to the fact that these crosswords tend to have fewer theme- or pun-based clues, and tend to reuse previously seen clues. For Monday puzzles, we can typically expect to fill in at least 90% of the letters correctly. We even got one completely right! As the week goes on and puzzles get harder, our performance decreases. We still tend to exceed 50% accuracy even on the harder puzzles.