# Solve a maze recursive

• 09-19-2006
BENCHMARKMAN
Solve a maze recursive
I'm trying to solve a maze recursively. I wrote the code but I keep getting an infinte loop. I looked online and the code and logic is the same. Can somebody tell me what I'm doing wrong? Thanks

Its a 5x5 maze and here is the maze

xsxxx
x---x
x--xx
e---x
xx-xx

Code:

```bool solveMaze(int startRow, int startCol, char maze [][5]){                  if(maze[startRow][startCol]=='e'){     return true;   }//end if     if(startRow>4 || startCol>4 || startRow<0 || startCol<0){     return false;   }//end if       if(maze[startRow][startCol]=='x'){     return false;   }//end if      if(solveMaze(startRow+1, startCol, maze)){                              return true;        }//end if     if(solveMaze(startRow, startCol+1, maze)){     return true;   }//end     if(solveMaze(startRow-1, startCol, maze)){                            return true;        }//end if      if(solveMaze(startRow, startCol-1, maze)){     return true;   }//end if     return false;  }//end solveMaze```
• 09-19-2006
Salem
You need to store in the maze some kind of 'visited' flag, otherwise you just keep going over the same ground.
• 09-19-2006
theFOX
Here is the solution using a some kind of visited flag so that you donnot enter those cells that makes you unable to move again. If it is not clear, i will make an array of flags, each cell will hold a value ( 0 >> 4 ), if the value of cell (r, c) equ 4 that means, there is no possible way from this cell except the one that leads you to that cell. so that we donnot want to visite this cell ( with the value 4 ) again.

i considered the start position will be 0,1 and, the maze size will be 5 x 5

- In your case you considered the maze always has a solution, if it doesn't have a solution, the program will run into stack overflow !!-

btw, it is 2 AM here :sleepy: so donnot flame me if that doesn't work !!!!!!!

Code:

```#include <fstream> using namespace std; char maze  [6][6] = {{0}}; char bmaze [6][6] = {{0}}; ifstream fin  ("maze.in"); ofstream fout ("maze.out"); int solution_count = 1; bool solved; short e_row, e_col; void GO(int r, int c) {         if ( solved )                 return;         else if ( r == 5 || c == 5 || r < 0 || c < 0 )                 return;         else if ( maze[r][c] == 'x' || bmaze[r][c] == 4 )                 return;         else if ( maze[r][c] == 'e' ){                                 solved = true;                 e_row = r;                 e_col = c;                 solution_count ++;                 return;         }         GO(r+1, c);                 bmaze[r][c] ++;         GO(r, c+1);                 bmaze[r][c] ++;         GO(r, c-1);                 bmaze[r][c] ++;         GO(r-1, c);                        bmaze[r][c] ++; } int main() {         int size = 5;                 int i;         for(i=0 ;i <5;i++)                 fin.getline(maze[i], 80);         GO(0, 1);         fout << solved << endl;         fout << e_row << "," << e_col << endl;         fout << solution_count << endl;                 return 0; }```
• 09-19-2006
Salem
We try to get people to think for themselves a bit, not post complete alternative answers right away.
• 09-19-2006
VirtualAce
There is a much easier way.
Stacks, stacks, stacks.
You need two operations: push value, pop value.

Also a maze solver is not much different than a maze creation program.