title: How to solve crossword (NP-Hard)?
body: <p>I am currently doing an assignment and I'm stuck with the approach.</p>
  
  <p>I have a crossword problem which consists of an empty grid (no solid square as a conventional crossword would), with a varied width and height between 4 and 400 (inclusive).</p>
  
  <p><strong>Rules:</strong>  </p>
  
  <ol>
  <li>Words are part of the input - a list of 10 - 1000 (inclusive) English words of varying lengths.</li>
  <li>A horizontal word can only intersect a vertical word.  </li>
  <li>A vertical word can only intersect a horizontal word. </li>
  <li>A word can only intersect 1 or 2 other words.  </li>
  <li>Each letter is worth one point.</li>
  <li>Words must have a 1 grid space gap surrounding it unless it is a part of an intersecting word. </li>
  </ol>
  
  <p><strong>Example:</strong>  </p>
  
  <pre><code>X X X X X X  
  X B O S S X  
  X X X X X X  
  </code></pre>
  
  <p><strong>Goal:</strong><br>
  Get the maximum possible score within a 5 minute time limit.</p>
  
  <p><strong>So far:</strong><br>
  After some research I am aware that this is an NP-Hard problem. Thus the most optimal solution cannot be calculated because every combination cannot be examined.</p>
  
  <p>The easiest solution would appear to be to sort the words according to length and inserting the highest scoring words for maximum score (greedy algorithm).</p>
  
  <p>I’ve also been told a recursive tree with the nodes consisting of alternative equally scoring word insertions and the knapsack algorithm apply to this problem (not sure what the implementation would look like).</p>
  
  <p><strong>Questions:</strong>  </p>
  
  <ol>
  <li>What allows me to check the maximum number of combinations within a 5 minute time span that scales accordingly to the maximum possible word list and grid size?</li>
  <li>What heuristics might I apply when inserting words?</li>
  </ol>
  
  <p>Btw the goal here is to get the best possible solution in 5 minutes.
  To clarify each letter of a valid word is worth 1 point, thus a 5 letter word is worth 5 points.</p>
  
  <p>Thanks in advance I have been reading a lot of mathematical notation on crossword research papers all day which has seem to have lead me in a circle.</p>