title: Recursive backtracking in Java for solving a crossword
body: <p>I need to solve a crossword given the initial grid and the words <em>(words can be used more than once or not at all)</em>.</p>
  
  <p>The initial grid looks like that:</p>
  
  <pre><code>++_+++
  +____+
  ___+__
  +_++_+
  +____+
  ++_+++
  </code></pre>
  
  <p>Here is an example word list:</p>
  
  <pre><code>pain
  nice
  pal
  id
  </code></pre>
  
  <p>The task is to fill the placeholders <em>(horizontal or vertical having length > 1)</em> like that:</p>
  
  <pre><code>++p+++
  +pain+
  pal+id
  +i++c+
  +nice+
  ++d+++
  </code></pre>
  
  <p>Any correct solution is acceptable, and it's guaranteed that there's a solution.</p>
  
  <hr>
  
  <p>In order to start to solve the problem, I store the grid in 2-dim. char array and I store the words by their length in the list of sets: <code>List&lt;Set&lt;String&gt;&gt; words</code>, so that e.g. the words of length 4 could be accessed by <code>words.get(4)</code></p>
  
  <p>Then I extract the location of all placeholders from the grid and add them to the list (stack) of placeholders:</p>
  
  <pre><code>class Placeholder {
      int x, y; //coordinates 
      int l; // the length
      boolean h; //horizontal or not
      public Placeholder(int x, int y, int l, boolean h) {
          this.x = x;
          this.y = y;
          this.l = l;
          this.h = h;
      }
  }
  </code></pre>
  
  <p>The main part of the algorithm is the <code>solve()</code> method:</p>
  
  <pre><code>char[][] solve (char[][] c, Stack&lt;Placeholder&gt; placeholders) {
      if (placeholders.isEmpty())
          return c;
  
      Placeholder pl = placeholders.pop();
      for (String word : words.get(pl.l)) {
          char[][] possibleC = fill(c, word, pl); // description below
          if (possibleC != null) {
              char[][] ret = solve(possibleC, placeholders);
              if (ret != null)
                  return ret;
          }
      }
      return null;
  }
  </code></pre>
  
  <p>Function <code>fill(c, word, pl)</code> just returns a new crossword with the current word written on the current placeholder <em>pl</em>. If <em>word</em> is incompatible with <em>pl</em>, then function returns null.</p>
  
  <pre><code>char[][] fill (char[][] c, String word, Placeholder pl) {
  
      if (pl.h) {
          for (int i = pl.x; i &lt; pl.x + pl.l; i++)
              if (c[pl.y][i] != '_' &amp;&amp; c[pl.y][i] != word.charAt(i - pl.x))
                  return null;
          for (int i = pl.x; i &lt; pl.x + pl.l; i++)
              c[pl.y][i] = word.charAt(i - pl.x);
          return c;
  
      } else {
          for (int i = pl.y; i &lt; pl.y + pl.l; i++)
              if (c[i][pl.x] != '_' &amp;&amp; c[i][pl.x] != word.charAt(i - pl.y))
                  return null;
          for (int i = pl.y; i &lt; pl.y + pl.l; i++)
              c[i][pl.x] = word.charAt(i - pl.y);
          return c;
      }
  }
  </code></pre>
  
  <h2>Here is the full code on <a href="http://rextester.com/MEYRW1661" rel="nofollow noreferrer">Rextester</a>.</h2>
  
  <hr>
  
  <p>The problem is that my backtracking algorithm doesn't work well. Let's say this is my initial grid:</p>
  
  <pre><code>++++++
  +____+
  ++++_+
  ++++_+
  ++++_+
  ++++++
  </code></pre>
  
  <p>And this is the list of words:</p>
  
  <pre><code>pain
  nice
  </code></pre>
  
  <p>My algorithm will put the word <code>pain</code> vertically, but then when realizing that it was a wrong choice it will backtrack, but by that time the initial grid will be already changed and the number of placeholders will be reduced. How do you think the algorithm can be fixed?</p>