Thread: backtracking!!

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    33

    backtracking!!

    HELLO EVERYONE, I have an assignment question in which i have to find all the poosible solution to solve a maze.I need to build the algorithm through recursion.I have done it for single path but now i have to find all the possible paths.For this,i guess,i have to open all the "visited" cells again so that in backtracking,function again goes through another path.
    My question is that where should i "open" all the "visited cells again so that while backtracking,function receives it as "unvisited".I am pasting my code here.
    Code:
    #include <iostream>
    #include <fstream>
    
    using namespace std;
    
    /* ============================= */
    /* =====  Global Variables ===== */
    /* ============================= */
    enum gameStatus {pending, success, impossible};
    
    /* =============================== */
    /* ===== Function Prototypes ===== */
    /* =============================== */
    void ReadMaze(char Maze[10][10],int& row,int& col,int& mouse,int& cheese);
    void DrawMaze(char Maze[10][10],int& row,int& col,int& mouse,int& cheese);
    void EscapeMaze(char Maze[10][10], int cpx, int cpy, const int spx, const int spy, const int epx, const int epy, 
    				const int hbx, const int hby, gameStatus& status,int& nosol,int row,int col,int cheese,int mouse);
    
    /* ========================= */
    /* ===== Main Function ===== */
    /* ========================= */
    int main()
    {
    	system("cls");
    	
    	// Defining maze array and positioning variables
        int row,col,mouse,cheese;
        char Maze[10][10];
        ReadMaze(Maze,row,col,mouse,cheese);
        cout<<row<<col<<mouse<<cheese<<endl;
        
        for (int i=0;i<row;i++)
        {
            for (int j=0;j<col;j++)
            {
                cout<<Maze[row][col]<<endl;
            }
        }
      	int spx = mouse;
    	int spy = col-1;
    	int epy = 0;
    	int epx = 0;
    	int hbx = 0;
    	int hby = 0;
    	int cpx = spx;
    	int cpy = spy;
    	int nosol = 0;
    	
    	
    	// Defining status variable and setting its initial value
    	gameStatus status;
        status = pending;
    	
    	
    	EscapeMaze(Maze, cpx, cpy, spx, spy, epx, epy, hbx, by,status,nosol,row,col,cheese,mouse);
    	cout<<"solutions:"<<nosol<<endl;
        if (status == impossible)
    		cout << "No path exists" << endl;
    	else
    		DrawMaze(Maze,row,col,mouse,cheese);
    	
    	system("pause");
    	return 0;
    } /* end main */
    
    /* ================================ */
    /* ===== Function Definitions ===== */
    /* ================================ */
    
    
         
    
    
    void ReadMaze(char Maze[10][10],int& row,int& col,int& mouse,int& cheese)
    {
        int m = -1,n = 0;   
        ifstream ifile;
        
        ifile.open("input.txt");
        
        ifile>>row;
        ifile>>col;
        ifile>>mouse;
        ifile>>cheese;
        
       
        
    	while(!ifile.eof())
    	{
    		m++;
    		for (int n = 0; n < col ; n++)
    		{
    			ifile >> Maze[m][n];
    		} /* end for */
    	} /* end while */
    	
    	ifile.close();
    	 // cout<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
    	
    } /* end ReadMaze */
    
    void DrawMaze(char Maze[10][10],int& row,int& col,int& mouse,int& cheese)
    {
    	for (int i = 0; i < row; i++)
    	{
    		for (int j = 0; j < col; j++)
    		{
    			cout << Maze[i][j] << " ";
    		} /* end for */
    		cout << endl;
    	} /* end for */
    } /* end DrawMaze */
    
    void EscapeMaze(char Maze[10][10], int cpx, int cpy, const int spx, const int spy, const int epx, const int epy, 
    				const int hbx, const int hby, gameStatus& status,int& nosol,int row,int col,int cheese,int mouse)
    { 
           
     
        DrawMaze(Maze,row,col,mouse,cheese);
        cout<<endl;
     //   system("pause"); 
    	if (cpx <= row && cpy <= col && cpx >= hbx && cpy >= hby)
    	{
    		if (cpx == cheese && cpy == cheese)
    		{
    			Maze[cheese][cheese] = '*';
    	        status = success;
    	        nosol++;
         			
    		} /* end if */
    		
    	
    		else
    		{
    			Maze[cpy][cpx] = '*';
    		
    			// Check positions for all directions
    
    			if ((Maze[cpy][cpx+1] == '0') || (Maze[cpy][cpx+1] == 'X')) 
        			EscapeMaze(Maze, cpx+1, cpy, spx, spy, epx, epy, hbx, hby, status, nosol, row, col, cheese,mouse); // right
    			
                if ((Maze[cpy][cpx+2] == '0') || (Maze[cpy][cpx+2] == 'X')) 
        			EscapeMaze(Maze, cpx+2, cpy, spx, spy, epx, epy, hbx, hby, status, nosol, row, col, cheese,mouse); // right
    			            
                if ((Maze[cpy][cpx-1] == '0') || (Maze[cpy][cpx-1] == 'X'))
    				EscapeMaze(Maze, cpx-1, cpy, spx, spy, epx, epy, hbx, hby, status, nosol,row, col, cheese,mouse); // left
    			
    			if ((Maze[cpy][cpx-2] == '0') || (Maze[cpy][cpx-2] == 'X'))
    				EscapeMaze(Maze, cpx-2, cpy, spx, spy, epx, epy, hbx, hby, status, nosol,row, col, cheese,mouse); // left
    						
                if ((Maze[cpy-1][cpx] == '0') || (Maze[cpy-1][cpx] == 'X'))
    				EscapeMaze(Maze, cpx, cpy-1, spx, spy, epx, epy, hbx, hby, status, nosol, row, col, cheese,mouse); // up
    	
    	        if ((Maze[cpy-2][cpx] == '0') || (Maze[cpy-2][cpx] == 'X'))
    				EscapeMaze(Maze, cpx, cpy-2, spx, spy, epx, epy, hbx, hby, status, nosol, row, col, cheese,mouse); // up
    	
                Maze[cpy][cpx] = '0';  //I think here it should "open" again.. 
                
                
         
    	
    			if (status != success)
    			{
    				if (cpx == spx && cpy == spy)
    					status = impossible;
    				
                    Maze[cpy][cpx] = '1';
    			} /* end if */
    		} /* end else */
    
    	} /* end if */
    } /* end EscapeMaze */

    The main problem is in Escape maze function.Can anyone tell me that where should i "open" the cells again?

  2. #2
    Registered User
    Join Date
    Feb 2009
    Posts
    37
    I'm not sure how you are representing the maze data. But you need to be keeping track of the steps you have taken as you traverse the maze. You could have an array, and each time you take a step, add to the array, indicating which direction you just went. At the beginning of the recursive function, add the step you are taking, and at the end of the function, remove it. When you find a successful path, just use the data in the array, and print it out.

  3. #3
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    personally, I think its easier than you are making it. You solve it recursively by basically saying

    the shortest path from the current cell to the exit is the shortest path among the neighboring cells that haven't already been checked, unless one of those cells is the exit, in which case that is the shortest path.

  4. #4
    Registered User
    Join Date
    Mar 2009
    Posts
    33
    Here is what my maze look like


    X 0 C
    0 0 C
    C 0 M

    I have to start from "M" and should reach to "X".But my code runs only for single path.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    fun( )
        here = used
    
        if here is exit
             win
        if unused north
            fun( north )
        if unused east
            fun( east )
        if unused south
            fun( south )
        if unused west
            fun( west )
    
        dead end, return
    That's pretty much all you need.


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Mar 2009
    Posts
    33

    Smile

    its done!!thanx

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. backtracking
    By spank in forum C Programming
    Replies: 1
    Last Post: 04-29-2006, 01:40 AM
  2. Backtracking
    By ilmarculin in forum C Programming
    Replies: 6
    Last Post: 02-13-2005, 08:00 AM
  3. Backtracking
    By darnok in forum C++ Programming
    Replies: 6
    Last Post: 07-29-2004, 12:08 PM
  4. about the backtracking method and maze
    By yifong84 in forum C++ Programming
    Replies: 2
    Last Post: 03-05-2004, 09:33 AM
  5. Help needed with backtracking
    By sjalesho in forum C Programming
    Replies: 1
    Last Post: 11-09-2003, 06:28 PM