title: Empty crossword solver in Python
body: <p>I'm given a matrix containing a blueprint of a crossword puzzle - unfilled, of course. The goal is to fill the whole puzzle - it's a task from Checkio, and I've been struggling with this for quite some time now.</p>
  
  <p>From what I understand of complexity, there's no perfect algorithm for this problem. Still, there has to be the best way to do this, right? I've tried some different things, and results were not that good with increasing number of words in the crossword and/or dictionary.</p>
  
  <p>So, some of the things I've tried:</p>
  
  <ul>
  <li>simple brute forcing. Did not work at all, as it has been ignoring
  and overwriting intersections.</li>
  <li>brute forcing while keeping all the relevant data - worked as expected with a specific dictionary, turned to hell with a
  moderately big one even with word-length optimization. Figures.</li>
  <li>blind intersection filling - the idea where I thought it would be better not to bother with the intersecting words, instead focusing
  on the letters. Like start with As and check if you can fill the
  whole crossword with these restrictions. If it did not work for some
  word, increment one of the letters and try the whole thing again.
  Results were abysmal as you can expect.</li>
  <li>recursive exploring - worked perfectly on more simple blueprints, but fell flat with more complex ones. There was an issue with simple
  loops which was resolved simply enough, but I did not find a
  reasonable solution for the situation where the path splits and then
  rejoins several further splits later (so there's nothing left to
  solve for the second branch, but it doesn't know that).</li>
  <li>minimizing intersections - haven't tested this yet, but it looks promising. The idea is that I find the shortest list of words
  containing all intersections... that also don't intersect with each
  other. Then I can just use a generator for each of those words, and
  then check if the depending words with those intersections exist. If
  they don't, I just grab the next word from a generator.</li>
  </ul>
  
  <p>And this is where I'm currently at. I decided to ask about this here as it's already at that point where I think it took more time than it should have, and even then my latest idea may not even be the proper way to do it.</p>
  
  <p>So, what <em>is</em> the proper way to do it?</p>
  
  <p>Edit: 
  Input is a list of strings representing the crossword and a list of strings representing the dictionary. Output is a list of strings representing the filled crossword.</p>
  
  <p>And example of a crossword: </p>
  
  <pre><code>['...XXXXXX', 
   '.XXX.X...', 
   '.....X.XX', 
   'XXXX.X...', 
   'XX...X.XX', 
   'XX.XXX.X.', 
   'X......X.', 
   'XX.X.XXX.', 
   'XXXX.....']
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/ofiXW.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ofiXW.png" alt="the crossword"></a></p>
  
  <p>The output would be a similar list with filled letters instead of dots.</p>
  
  <p>Note that the 'dictionary' is just that, a small English dictionary and not a list of words fitted as answers for this puzzle.</p>