title: Word Solver - All Directions
body: <p>I created a word solver for all directions. It finds words horizontally, vertically and reverse. However, I am having problems making it go all directions. So to take "hello" in:</p>
  
  <pre><code>H  E  i  l
  x  L  p  q
  c  L  O  m
  </code></pre>
  
  <p>Anyone can point me on how to do that? Here is my algorithm to that searches for the words (in C++):</p>
  
  <pre><code>/*
   * For loops that search each row, each column in all 8 possible directions.
   */
  void Scramble::solve() {
  
  cout &lt;&lt; "Output:" &lt;&lt; endl;
  
  for (int row = 0; row &lt; getRows(); row++) {
      for (int col = 0; col &lt; getCols(); col++)
          for (int rowDir = -1; rowDir &lt;= 1; rowDir++)
              for (int colDir = -1; colDir &lt;=1; colDir++)
                  if (rowDir != 0 || colDir != 0)
                      findWords(row, col, rowDir, colDir);
  }
  }
  
  /*
   * Finds the matches in a given direction. Also calls verifyWord() to verify that the
   * current sequence of letters could possibly form a word. If not, search stops.
   */
  void Scramble::findWords(int startingRow, int startingCol, int rowDir, int colDir) {
  
  int searchResult;
  string sequence = "";
  sequence = sequence + wordsArr[startingRow][startingCol];
  
  for (int i = startingRow + rowDir, j = startingCol + colDir; i &gt;= 0 &amp;&amp; j &gt;= 0
  &amp;&amp; i &lt; getRows() &amp;&amp; j &lt; getCols(); i = i + rowDir, j = j + colDir) {
  
      sequence = sequence + wordsArr[i][j];
  
      if (sequence.length() &gt;= 3) {
  
          searchResult = verifyWord(words, sequence);
  
          if ((unsigned int)searchResult == words.size())
              break;
  
          if (words[searchResult].rfind(sequence) &gt; words[searchResult].length())
              break;
  
          if (words[searchResult] == (sequence))
              cout &lt;&lt; sequence &lt;&lt; endl;
      }
  }
  }
  
  /*
   * Performs the verifyWord search method.
   * Searches the word to make sure that so far, there is possibly that the current sequence
   * of letter could form a word. That is to avoid continuing to search for a word
   * when the first sequence of characters do not construct a valid word in the dictionary.
   *
   * For example, if we have 'xzt', when this search is done it prevents the search
   * to continue since no word in the dictionary starts with 'xzt'
   */
  int Scramble::verifyWord(vector&lt;string&gt; words, string str) {
  
  int low = 0;
  int mid = 0;
  int high = words.size();
  
  while (low &lt; high) {
  
      mid = (low + high) / 2;
  
      if (str &gt; words[mid]) {
          low = mid + 1;
      }
  
      else if (str &lt; words[mid]) {
          high = mid - 1;
      }
  
      else
          return mid;
  }
  }
  </code></pre>