title: C++: Recursive backtracking boggle grid
body: <p>I realize this code might be a bit dense to read, what I´ve tried to do is to adapt a standard recursive  maze-solving algorithm - where all directions are tried until a solution is found, to an algorithm for the game 'boggle' that checks if the target word can formed on the grid by going in either of the four directions. I realize this code got more than one bug, but I´d like some input on how to solve the most important like that the direction and way it is searching the grid is obviously not working.</p>
  
  <p>Console output:</p>
  
  <pre><code>Enter word: 
  aefn
  First matching letter found at [row: 0] [col: 0]
  findNext: Point location: Y[0] X[0]
  
  Point location: Y[0] X[-1]
  A //(This is the algorithm trying to find "targetWord" on grid "currentWord")
  Point location: Y[1] X[0]
  AA
  Point location: Y[0] X[0]
  AAE
  Point location: Y[0] X[-1]
  AAEA
  Point location: Y[1] X[0]
  AAEAA
  Point location: Y[0] X[1]
  AAEAAA
  Point location: Y[-1] X[0]
  AAEAAAA
  Point location: Y[1] X[1]
  AAEE
  Point location: Y[1] X[0]
  AAEEU
  Point location: Y[2] X[1]
  AAEEUU
  Point location: Y[1] X[2]
  AAEEUUU
  Point location: Y[0] X[1]
  AAEEUUUU
  Point location: Y[0] X[2]
  AAEEE
  Point location: Y[-1] X[1]
  AAEEEE
  Point location: Y[0] X[1]
  AAA
  Point location: Y[1] X[-1]
  AAAE
  Point location: Y[2] X[0]
  AAAEE
  Point location: Y[1] X[1]
  AAAEEE
  Point location: Y[0] X[0]
  AAAEEEE
  Point location: Y[-1] X[0]
  AAAA
  </code></pre>
  
  <p>Code:</p>
  
  <pre><code>enum Direction { NORTH,
                   EAST,
                   SOUTH,
                   WEST };
  
  
  
  
  
  
  /**  Attempts to find a matching letter on the grid to the first letter in the 
    *  targetWord, if found it stores it location in grid in 'point' and calls
    *  findNext() with the location of matching letter stored in the 'point'.  
    */
  bool findMatchingFirstLetter(Grid&lt;char&gt; &amp;cubeGrid, string currentWord, string targetWord, int index)
  {
  
      for (int row = 0; row &lt; cubeGrid.numRows(); row++)
      {
          for (int col = 0; col &lt; cubeGrid.numCols(); col++)
          {
              if (cubeGrid.get(row, col ) == targetWord[0])
              {
                  cout &lt;&lt;  "First matching letter found at [row: " &lt;&lt; row &lt;&lt; "] [col: " &lt;&lt; col &lt;&lt; "]" &lt;&lt; endl;
                  GPoint point(col, row);
                  cout &lt;&lt; "findNext: " &lt;&lt; findNextRecur(cubeGrid, currentWord, targetWord, index, point) &lt;&lt; endl;
  
              }
          }
      }
      return false;
  }
  
  
  
  /**  Recursive function.
    *  Exhaustively searches the grid for all possible combinations, moving in all 
    *  compass directions. */
  bool findNextRecur(Grid&lt;char&gt; &amp;cubeGrid, string currentWord, string targetWord, int index, GPoint point)
  {
      cout &lt;&lt; "Point location: Y[" &lt;&lt; point.getY() &lt;&lt; "] X[" &lt;&lt; point.getX() &lt;&lt; "]" &lt;&lt; endl;
      cout &lt;&lt; currentWord &lt;&lt; endl;
      if (currentWord == targetWord)
          return true;
      if (currentWord.length() &gt; targetWord.length() || 
          point.getX() &gt; cubeGrid.numCols() ||
          point.getX() &lt; 0 ||
          point.getY() &gt; cubeGrid.numRows() ||
          point.getY() &lt; 0)
      { return false; }
  
  
      for (Direction dir = NORTH; dir &lt;= WEST; dir++ )
      {
  
          if (findNextRecur(cubeGrid,
                            currentWord += cubeGrid.get(point.getY(), point.getX()),
                            targetWord,
                            index,    //index is currently not in use.
                            adjacentPoint(point, dir)))
          { return true; }
      }
  }
  
  
  
  GPoint adjacentPoint(GPoint point, Direction dir)
  {
      switch  (dir) {
          case NORTH: return GPoint(point.getY()-1, point.getX());
          case EAST: return GPoint(point.getY(), point.getX()+1);
          case SOUTH: return GPoint(point.getY()+1, point.getX());
          case WEST: return GPoint(point.getY(), point.getX()-1);
      }
      return point;
  }
  
  
  /**  Wrapper 
    */
  bool findWordOnGrid(Grid&lt;char&gt; &amp;cubeGrid, string word)
  {
      cout &lt;&lt; findMatchingFirstLetter(cubeGrid, "", toUpperCase(word), 0) &lt;&lt; endl;
      return true;
  }
  </code></pre>