title: Backtracking a maze using recursion in c++
body: <p>So looking at all of the other forums about solving a maze using recursion, none of them had helped me with my issue.</p>
  
  <p>I get a maze from an input file and there is a start and end position. I find the start pos pass the x and y by reference and recursively solve the maze. My issue is that every possible spot in the maze is getting filled with a sign. When only the solution path should be marked (the '@' is what we are to use to show the path of the solution)</p>
  
  <p>Here is what my code outputs when I complie and run:</p>
  
  <pre><code>    (2, 1)
      Found Exit
      |||||||||||
      |@@@|||@@@|
      |@|@@@@@|E|
      |||||||||||
  
      (5, 5)
      Found Exit
      ||||||||||||||||
      |@@@   |NNNN|N||
      |@|@||||N||NNN||
      |@|@@@@@@|||||||
      |@||||||@|E@@  |
      |@|||@@|@|||@|||
      |@|N||@|@@@@@|||
      |@|N||@||||||| |
      |@@@@@@        |
      ||||||||||||||||
  
      (1, 1)
      ||||||||||
      |NNN||  E|
      ||||||||||
  </code></pre>
  
  <p>As you can see, the 'N' are where the function found a dead end and needed to backtrack and erase them. The '@' sign is the correct path, it just doesn't erase when backtracking</p>
  
  <p>I believe my issues is the the find_exit function or at_end function</p>
  
  <p>Here is the code: </p>
  
  <pre><code>// "maze.h"
  
  //header file
  #include &lt;iostream&gt;
  #include &lt;string&gt;
  
  #ifndef MAZE
  #define MAZE
  
  using std::cout;
  using std::endl;
  using std::cin;
  using std::string;
  
  
  /*
  Writes to a string array containing:
  * the your (the student author’s) Campus Username (at index 0)
  * and Student ID# (at index 1).
  Takes as input a pre-existing length-2 string array.
  */
  void get_identity(string my_id[]);
  
  
  /**
  Use this to help you enumerate the directions.
  Gets passed into one function below.
  **/
  enum direction
  {
      NORTH,
      SOUTH,
      EAST,
      WEST
  };
  
  
  /**
  Creates a dynamically allocated array of strings.
  Returns a pointer to that array.
  **/
  string * build_matrix(int rows);
  
  
  /**
  Fills the matrix with one line per string in the array.
  Use the getline method.
  Why don't you need to send in cols?
  **/
  void fill_matrix(string *matrix, int rows);
  
  
  /**
  Print the matrix as in the sample_output.txt
  **/
  void print_matrix(string *matrix, int rows);
  
  
  /**
  Delete the dynamically allocated array of strings.
  Why don't you need to send in cols?
  **/
  void delete_matrix(string *matrix, int rows);
  
  
  /**
  Finds the starting position of Niobe.
  Note: x and y are passed by reference; what does this do for you?
  Why don't you need cols here? Hint: not the same reason as last two.
  **/
  void find_start(string *matrix, int rows, int &amp;x, int &amp;y);
  
  
  /**
  This is the recursive backtracking function you need to write.
  It should return true if you found the solution,
  and false if there is no solution.
  It should leave a trail of @ signs along the path to the solution.
  Make sure to build your solution with strong emphasis on the pseudocode;
  do not try to code it first, first work out the solution on paper/markerboard.
  **/
  bool find_exit(string *matrix, int x, int y);
  
  
  /**
  Returns true if x and y are the final exit location,
  and false otherwise.
  **/
  bool at_end(string *matrix, int x, int y);
  
  
  /**
  Returns true if the position indexed by x and y is a valid move,
  and false otherwise.
  What is a valid move?
  **/
  bool valid_move(string *matrix, int x, int y, direction d);
  
  
  #endif
  #include &lt;fstream&gt;
  #include &lt;limits&gt;
  
  using std::ifstream;
  
  void get_identity(string my_id[])
  {
      my_id[0] = "sra9wb";
      my_id[1] = "16781948";
  
      //output
      cout &lt;&lt; "MST Campus Username: " &lt;&lt; my_id[0] &lt;&lt; endl;
      cout &lt;&lt; "Student ID: " &lt;&lt; my_id[1] &lt;&lt; endl;
  }
  
  string *build_matrix(int rows)
  {
      string *matrix = new string[rows]; //allocating memory for the matrix
  
      return matrix;
  }
  
  void fill_matrix(string *matrix, int rows)
  {
      ifstream file_in("sample_input.txt");
      int x = 0;
      int y = 0;
      bool solved = false;
  
      while (file_in)
      {
          file_in &gt;&gt; rows;
  
          if (rows == 0)
              return;
  
          matrix = build_matrix(rows);
  
          file_in.ignore(std::numeric_limits&lt;std::streamsize&gt;::max(), '\n'); //Grab line until '\n' then toss it
  
          for (int i = 0; i &lt; rows; i++)
          {
              getline(file_in, matrix[i]);//fillinf matrix with file_in from text file
          }
          find_start(matrix, rows, x, y);
          find_exit(matrix, x, y);
          print_matrix(matrix, rows);
          cout &lt;&lt; endl;
          delete_matrix(matrix, rows);
      }
  }
  
  void print_matrix(string *matrix, int rows)
  {
      for (int i = 0; i &lt; rows; i++) //increment through the row of the matrix
      {
          cout &lt;&lt; matrix[i] &lt;&lt; endl; //print eack row
      }
  }
  
  void delete_matrix(string *matrix, int rows)
  {
      delete[] matrix; //delete the matrix
      matrix = NULL;   //set equal to null for no hanging pointers
  }
  
  void find_start(string *matrix, int rows, int &amp;x, int &amp;y)
  {
      for (int i = 0; i &lt; rows; i++) //increment through the rows
      {
          string column;
          column = matrix[i]; //set the incremented row to string column
  
          for (int j = 0; j &lt; column.length(); j++) //increment through the length of column
          {
              if (column[j] == 'N') //if the index of column matches N
              {
                  x = i; //x is equal to i because of the 1st for loop
                  y = j; //y is eqyal to j because of the 1st for loop
              }
          }
      }
      cout &lt;&lt; "(" &lt;&lt; x &lt;&lt; ", " &lt;&lt; y &lt;&lt; ")" &lt;&lt; endl;
  
  }
  
  bool find_exit(string *matrix, int x, int y) //first iteration of function passing in coords of N's starting pos
  {
      //check if we reached the end of the maze
      if (at_end(matrix, x, y) == true)
          return true;
  
      //sets the starting position to @
      matrix[x][y] = 'N';
  
      //recursive search for out goal
      if (valid_move(matrix, x, y, NORTH) &amp;&amp; find_exit(matrix, x - 1, y))
      {
          matrix[x][y] = '@';
          return true;
      }
      else if (valid_move(matrix, x, y, SOUTH) &amp;&amp; find_exit(matrix, x + 1, y))
      {
          matrix[x][y] = '@';
          return true;
      }
      else if (valid_move(matrix, x, y, WEST) &amp;&amp; find_exit(matrix, x, y - 1))
      {
          matrix[x][y] = '@';
          return true;
      }
      else if (valid_move(matrix, x, y, EAST) &amp;&amp; find_exit(matrix, x, y + 1))
      {
          matrix[x][y] = '@';
          return true;
      }
  
      //this line here is meant to print a space when backtracking occurs
      // matrix[x][y] = ' ';   
      // return false;
  }
  
  //this function returns true if you are at the end of the maze
  bool at_end(string *matrix, int x, int y)
  {
      if (matrix[x][y] == 'E')
      {
          cout &lt;&lt; "Found Exit" &lt;&lt; endl;
          return true;
      }
      else
          return false;
  }
  
  bool valid_move(string *matrix, int x, int y, direction d)
  {
      if (d == NORTH)
      {
          //check if north is clear
          if (matrix[x - 1][y] == ' ' || matrix[x - 1][y] == 'E')
              return true;
          else
              return false;
      }
      else if (d == EAST)
      {
          //check if EAST is clear
          if (matrix[x][y + 1] == ' ' || matrix[x][y + 1] == 'E')
              return true;
          else
              return false;
      }
      else if (d == SOUTH)
      {
          //check is south is clear
          if (matrix[x + 1][y] == ' ' || matrix[x + 1][y] == 'E')
              return true;
          else
              return false;
      }
      else if (d == WEST)
      {
          //check if west is clear
          if (matrix[x][y - 1] == ' ' || matrix[x][y - 1] == 'E')
              return true;
          else
              return false;
      }
      else
          return false;
  }
  
  //main
  
  // #include "maze.h"
  
  
  
  int main()
  {
      string *matrix = NULL;
      int rows = 0;
  
      fill_matrix(matrix, rows);
  
      return 0;
  }
  </code></pre>
  
  <p>The sample_input.txt document goes as follows:</p>
  
  <pre><code>4 11
  |||||||||||
  |   |||   |
  |N|     |E|
  |||||||||||
  
  10 16
  ||||||||||||||||
  |      |    | ||
  | | |||| ||   ||
  | |      |||||||
  | |||||| |E    |
  | |||N | ||| |||
  | | || |     |||
  | | || ||||||| |
  |              |
  ||||||||||||||||
  
  3 10
  ||||||||||
  |N  ||  E|
  ||||||||||
  
  0 0
  </code></pre>
  
  <p>These are the mazes that we are supposed to solve.</p>
  
  <p>Also I am not allowed to edit the header file.</p>
  
  <p>And this is how the output is supposed to look:</p>
  
  <pre><code>    Map 0 -- Solution found:
      |||||||||||
      |@@@|||@@@|
      |N|@@@@@|E|
      |||||||||||
  
      Map 1 -- Solution found:
      ||||||||||||||||
      |@@@   |    | ||
      |@|@|||| ||   ||
      |@|@@@@@@|||||||
      |@||||||@|E@@  |
      |@|||N@|@|||@|||
      |@| ||@|@@@@@|||
      |@| ||@||||||| |
      |@@@@@@        |
      ||||||||||||||||
  
      Map 2 -- No solution found:
      ||||||||||
      |N  ||  E|
      ||||||||||
  </code></pre>