title: How to find all the possible words using adjacent letters in a matrix
body: <p>I have the following test matrix:</p>
  
  <pre>
  a l i
  g t m
  j e a
  </pre>
  
  <p><em>I intend to create an algorithm that helps me find every possible word from a given minimum length to a maximum length using adjacent letters only.</em></p>
  
  <p>For example:</p>
  
  <p>Minimum: 3 letters</p>
  
  <p>Maximum: 6 letters</p>
  
  <p>Based on the test matrix, I should have the following results:</p>
  
  <ul>
  <li>ali</li>
  <li>alm</li>
  <li>alg</li>
  <li>alt</li>
  <li>ati</li>
  <li>atm</li>
  <li>atg</li>
  <li>...</li>
  <li>atmea</li>
  </ul>
  
  <p>etc.</p>
  
  <p>I created a test code (C#) that has a custom class which represents the letters.</p>
  
  <p>Each letter knows its neighbors and has a generation counter (for keeping track of them during traversal).</p>
  
  <p>Here is its code:</p>
  
  <pre><code>public class Letter
  {
      public int X { get; set; }
      public int Y { get; set; }
  
      public char Character { get; set; }
  
      public List&lt;Letter&gt; Neighbors { get; set; }
  
      public Letter PreviousLetter { get; set; }
  
      public int Generation { get; set; }
  
      public Letter(char character)
      {
          Neighbors = new List&lt;Letter&gt;();
          Character = character;
      }
  
      public void SetGeneration(int generation)
      {
          foreach (var item in Neighbors)
          {
              item.Generation = generation;
          }
      }
  }
  </code></pre>
  
  <p>I figured out that if I want it to be dynamic, it has to be based on recursion.</p>
  
  <p>Unfortunately, the following code creates the first 4 words, then stops. It is no wonder, as the recursion is stopped by the specified generation level.</p>
  
  <p>The main problem is that the recursion returns only one level but it would be better to return to the starting point.</p>
  
  <pre><code> private static void GenerateWords(Letter input, int maxLength, StringBuilder sb)
      {
          if (input.Generation &gt;= maxLength)
          {               
              if (sb.Length == maxLength)
              {
                  allWords.Add(sb.ToString());
                  sb.Remove(sb.Length - 1, 1);
              }                
              return;
          }
          sb.Append(input.Character);
          if (input.Neighbors.Count &gt; 0)
          {
              foreach (var child in input.Neighbors)
              {
                  if (input.PreviousLetter == child)
                      continue;
                  child.PreviousLetter = input;
                  child.Generation = input.Generation + 1;
                  GenerateWords(child, maxLength, sb);
              }
          }
      }
  </code></pre>
  
  <p>So, I feel a little stuck, any idea how I should proceed?</p>