title: Crossword backtracking algorithm
body: <p>I am implementing crossword generator using backtracking according this algorithm:
  This is my pseudocode:</p>
  
  <pre><code>&gt;  solve(words,grid):    if words is empty:
  &gt;        if grid.isValudSol():
  &gt;           return grid
  &gt;        else:
  &gt;           return None    for each word in words:
  &gt;        possibleSol &lt;- grid.fillFirst(word)
  &gt;        ret &lt;- solve(words\{word},possibleSol)
  &gt;        if (ret != None):
  &gt;           return ret    return None
  </code></pre>
  
  <p>and this is my current code(C#):</p>
  
  <pre><code>Crossword.Crossword solveCrossword(List&lt;String&gt; words, Crossword.Crossword board){
          if (words.Count == 0)
          {
              return board;
          }
          //Create local copy of board
          Crossword.Crossword localBoard = new Crossword.Crossword(board);
  
          foreach (var word in words)
          {
              localBoard = new Crossword.Crossword(board);
              int positions = localBoard.getPositionsNumber(word);
              if(positions == 0){
                  return null;
              }
              for (int i = 0; i &lt; positions; ++i)
              {
                  localBoard = new Crossword.Crossword(board);
                  int addResult = localBoard.AddWord(word, i);        //possible solution is now in localBoard  
                  if (addResult != -1)
                  {
                      List&lt;String&gt; myWords = new List&lt;String&gt;();
                      for (int k = 0; k &lt; words.Count; ++k)
                      {
                          if (words[k] != word)
                              myWords.Add(words[k]);
                      }
                      Crossword.Crossword ret = solveCrossword(myWords, localBoard);
                      if (ret != null)
                          return ret;
                  }
                  else
                  {
                      return null;
                  }
              }               
  
          }
          return null;
      }
  </code></pre>
  
  <p>My issue is that for grid NxN e.g. 6X6 i discover that for words number bigger than N my algorithm doesnt find solution - after 10 seconds or more ;/, for words number less or equal N it works OK
  thanks in advance for any kind of help!</p>