Solve a maze recursive

This is a discussion on Solve a maze recursive within the C++ Programming forums, part of the General Programming Boards category; I'm trying to solve a maze recursively. I wrote the code but I keep getting an infinte loop. I looked ...

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    47

    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

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    You need to store in the maze some kind of 'visited' flag, otherwise you just keep going over the same ground.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User theFOX's Avatar
    Join Date
    Sep 2006
    Location
    Egypt
    Posts
    6

    Lightbulb

    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;
    }

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    We try to get people to think for themselves a bit, not post complete alternative answers right away.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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.
    Last edited by VirtualAce; 09-19-2006 at 11:36 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 07:41 PM
  2. Recursive Stack Algorithm Maze Solver
    By unrestricted in forum C Programming
    Replies: 0
    Last Post: 09-04-2007, 03:11 AM
  3. Having trouble solving maze.
    By eurus in forum C Programming
    Replies: 3
    Last Post: 02-17-2006, 12:52 AM
  4. recursive maze help
    By chad101 in forum C++ Programming
    Replies: 1
    Last Post: 12-15-2005, 01:37 PM
  5. Recursive Solution to Any Maze And Stack Overflow Problems
    By PunkyBunny300 in forum C Programming
    Replies: 14
    Last Post: 12-14-2002, 06:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21