search

timpalpant / LittleBoxes

A crossword solver
GNU General Public License v3.0
1 stars 0 forks source link

Implement DictionarySolver #7

Open timpalpant opened 8 years ago

timpalpant commented 8 years ago

Use the Dictionary class to look up potential answers for a given clue. This solver is intended to be used after some letters have been filled in by the ClueDB solver, constraining the set of possible words.

timpalpant commented 8 years ago

This turns out to be hard! A non-trivial number of words have no constraints after the ClueDB phase, leaving a large combinatorial set of words to sift through.

A few things that I've tried and haven't worked:

  1. Reusing the clique solver algorithm with possible answers from the dictionary. Too large and slow (even if you optimize the data in the graph, or generate edges on-the-fly when doing Bron-Kerbosch).
  2. One-step lookahead, filling a clue only if it leaves at least one word available for each crossing clue. I didn't find a good way to deal with clues that have no answers in the Dictionary from the outset, but Dr. Fill mentions some variant of this that is useful, os maybe worth trying again.
  3. Randomly choosing words -- too much junk.
  4. Exploring branches by starting with the most-constrained (those with fewest unfilled letters). Like (2), it generated too many unfillable non-words in longer/later clues