I have this crossword but I seem to have lost all of the hints. However, the answers must be from this list of words. Can you figure it out for me?
As stated in one of the hints, this can be thought of as a branch and bound problem. There are too many possible permutations for brute-forcing to be feasible, even if words are only considered for valid lengths / solved letters. Thus, one must only consider words which fit into a partial solution, and all partial solutions must be considered to find the correct final solution.
To solve this problem in general (for arbitrary crossword size), one would need to dynamically keep track of partial solutions. However, in this scenario, the number of words is fixed, and thus a nested for loop solution can work.
The first required ingredient is a function that determines whether a word matches the "schema" for a given row or column. Such a function could look like this.
In addition to checking an individual word,
a function that returns ALL the words that match
a given schema is required.
this can be written like so.
Given all of the known connections between words
and the utility functions,
one can solve for the solution to the entire crossword.
Note that the order matters here.
Words should be solved such that early words have fewer possibilities.
eight_across is the first word selected.
This is chosen because there are 2 letters already known
and the word is long enough that there are fewer words
with this many letters overall.
Full solution: solution.py