I am new to C and am trying to write a program that reads a file, dynamically creates a 2D array, and fills the array with input from the file. Then it solves the maze using recursion. The text file looks like this:

The first 4 numbers dictate the amount of rows, amount of columns, and starting position (X,Y). "S" is the start, "O" the path, and "E" the end. I have no trouble with creating the array or filling the array, but when running the program, it encounters an error when calling the recursive function to solve the maze. This is the function:

bool mazeSolve(char **maze, int startRow, int startCol){
        
  char test = maze[startRow][startCol];
              
  //If maze finds end stop program (Base Case)
  if (test == 'E'){
     cout << "End reached" << endl;
     return true;
  }//End if for base case
       
  //If function can go right
  if (maze[startRow][startCol 1] == 'O'){
     maze[startRow][startCol] = 'P';
     return mazeSolve(maze, startRow, startCol 1);
  }
  
  //If function can go left
  if (maze[startRow][startCol-1] == 'O'){
     maze[startRow][startCol] = 'P';
     return mazeSolve(maze, startRow, startCol-1);
  }
  
  //If function can go up
  if (maze[startRow-1][startCol] == 'O' && startRow-1 >= 0){
     maze[startRow][startCol] = 'P';
     return mazeSolve(maze, startRow-1, startCol);
  }
  
  //If function can go down
  if (maze[startRow 1][startCol] == 'O'){
     maze[startRow][startCol] = 'P';
     return mazeSolve(maze, startRow 1, startCol);
  }
  
  //If function cannot find O's then it will backtrack
  //If function reaches wall, backtrack down
  if (maze[startRow 1][startCol] == 'P'){
        maze[startRow][startCol] = 'C';
        return mazeSolve(maze, startRow 1, startCol);
  }
  
  //If function reaches wall, backtrack up
  if (startRow-1 >= 0 && maze[startRow-1][startCol] == 'P'){
        maze[startRow][startCol] = 'C';
        return mazeSolve(maze, startRow-1, startCol);
  }
  
  //If function reaches wall, backtrack left
  if (maze[startRow][startCol-1] == 'P'){
        maze[startRow][startCol] = 'C';
        return mazeSolve(maze, startRow, startCol-1);
  }
  
  //If function reaches wall, backtrack right
  if (maze[startRow][startCol 1] == 'P'){
        maze[startRow][startCol] = 'C';
        return mazeSolve(maze, startRow, startCol 1);
  }      
  

I have googled and searched this site for similar problems but I seem to have a fundamental misunderstanding of recursion as I can't follow the solutions. I thought the bottom half would allow the function to backtrack until it found a new "O" and eventually an "E", but it is looping infinitely. My professor is asking for this to be done with if statements. Where did my logic go wrong? Any help would be greatly appreciated.

CodePudding user response：

I figured it out after some debugging. Rewrote the function from scratch. Thank you for everyone for your help. I added an out of bounds check and added a condition for the if statements to check for both 'O' and 'E'. Weirdly the backtracking if statements remained the same, even though I thought they were the issue.:

bool mazeSolve(char **maze, int startRow, int startCol){      
            
      //Output test message
      char test = maze[startRow][startCol];
      //cout << test << endl;
                  
      //If maze finds end stop program (Base Case)
      if (test == 'E'){
         cout << "End reached" << endl;
         return true;
      }//End if for base case
      
      //Out of bounds check
      if (startRow < 0 || startCol < 0 || startRow >= arrayRowSize || 
          startCol >= arrayColSize){
          cout << "bounds error";
          return false;   
      }//End out of bounds if
      
      //If function can go down
      if (maze[startRow 1][startCol] == 'O' || maze[startRow 1][startCol] == 'E'){
         maze[startRow][startCol] = 'P';
         //cout << "down" << endl;
         return mazeSolve(maze, startRow 1, startCol);
      } //End down if
      
      //If function can go right
      if (maze[startRow][startCol 1] == 'O' || maze[startRow][startCol 1] == 'E'){
         maze[startRow][startCol] = 'P';
         //cout << "right" << endl;
         return mazeSolve(maze, startRow, startCol 1);
      } //End right if
      
      //If function can go left
      if (maze[startRow][startCol-1] == 'O' || maze[startRow][startCol-1] == 'E'){
         maze[startRow][startCol] = 'P';
         //cout << "left" << endl;
         return mazeSolve(maze, startRow, startCol-1);
      } //End left if
      
      //If function can go up
      if (maze[startRow-1][startCol] == 'O' || maze[startRow-1][startCol] == 'E'){
         maze[startRow][startCol] = 'P';
         //cout << "right" << endl;
         return mazeSolve(maze, startRow-1, startCol);
      } //End up if     
      
      //If function cannot find O's then it will backtrack
      //If function reaches wall, backtrack down
      if (maze[startRow 1][startCol] == 'P'){
            maze[startRow][startCol] = '*';
            return mazeSolve(maze, startRow 1, startCol);
      } //End backtrack down if
      
      //If function reaches wall, backtrack up
      if (maze[startRow-1][startCol] == 'P'){
            maze[startRow][startCol] = '^';
            return mazeSolve(maze, startRow-1, startCol);
      } //End backtrack up if
      
      //If function reaches wall, backtrack left
      if (maze[startRow][startCol-1] == 'P'){
            maze[startRow][startCol] = '<';
            return mazeSolve(maze, startRow, startCol-1);
      } //End backtrack left if
      
      //If function reaches wall, backtrack right
      if (maze[startRow][startCol 1] == 'P'){
            maze[startRow][startCol] = '>';
            return mazeSolve(maze, startRow, startCol 1);
            //End backtrack right if
      } else 
         return false;//If all else fails, maze is unsolvable            
}

This solves the maze. My only issue now is error handling if the maze does not have an end. I edited the txt file to have no "E", and the function loops infinitely. I thought the final "else" statement would cover this, but it doesn't. What should I have done to handle the case of an unsolvable maze?

CodePudding user response：

When you backtrack, you first check if the search was successful, and then you try a different option if it wasn't, after reverting the attempt you just made.

An actual backtracking variant of your first non-base case would look like this:

if (maze[startRow][startCol 1] == 'O'){
     auto original = maze[startRow][startCol]; 
     maze[startRow][startCol] = 'P';
     if (mazeSolve(maze, startRow, startCol 1))
         return true;
     maze[startRow][startCol] = original;
}
// ... and keep going with the next attempt ...