Maze solver with DFS

Question

I am trying to solve the maze using DFS algorithm.ORDER: West- North-South-East My output works in this logic Labyrinth picture1. It should not go up after the point (3,3),because the order of priority is west. What should I do?

#include <stdio.h>

char matrix[8][8];

void File()
{
        int i,j;
  

    FILE *file1;
    file1=fopen("maze1.txt","r");
 
    for(i=0; i<8; i++){
        for(j=0;j<8;j++)
        {
        fscanf (file1, " %c", &matrix[i][j]);
        
        printf("%c ",matrix[i][j]);
       }
    printf("\n");
    }
}
void Print()
{
    int i,j;
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            printf("%c ",matrix[i][j]);
            }
    printf("\n");       
    }
}
void stepDFS()
{
    int i,j;
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            if(matrix[i][j] == 's')
            {
                
                    DFS(i,j);
                        
               
            
            }
            
        }
    printf("\n");       
    }
    
}
 DFS(int i,int j)
{
    if(matrix[i][j-1] == '-')
    {
        matrix[i][j-1] = '.';
        DFS(i,j-1);
    }
     if(matrix[i-1][j] == '-')
    {
        matrix[i-1][j] = '.';
        DFS(i-1,j);
    }
     if(matrix[i+1][j] == '-')
    {
        matrix[i+1][j] = '.';
        DFS(i+1,j);

    }
     if(matrix[i][j+1] == '-')
    {
        matrix[i][j+1] = '.';
       DFS(i,j+1);

    }
    
    
}
int main()
{
    File();
    Print();
    stepDFS();
    Print();
    return 0;
}

maze1.txt ( # wall - null . step)

# # # # # # # #  
# g - - # - - #       
# # # - - - # # 
# - # # - - - # 
# - - # - - - #
# - - - - # # # 
# - - # - - s #
# # # # # # # #

output

# # # # # # # #
# g . . # . . #
# # # . . . # #
# . # # . . . #
# . . # . . . #
# . . . . # # #
# . . # . . s #
# # # # # # # #

I don't know if this should be the output

# # # # # # # #  
# g . . # - - #       
# # # . . - # # 
# . # # . - - # 
# . . # . - - #
# . . . . # # # 
# - - # . . s #
# # # # # # # #

--------------UPDATE-------------- STEP BY STEP

#include <stdio.h>

char matrix[8][8];

void ReadFile()
{
    printf("\n\n\n                START MAZE    ");
    int x,y;
    FILE *file1;
    file1=fopen("myMaze.txt","r");
 
    for(x=0; x<8; x++){
        for(y=0;y<8;y++)
        {
        fscanf (file1, " %c", &matrix[x][y]);
        
      
       }
    printf("\n");
    }
}



void PrintMaze()
{ 
    int x,y;
    for(x=0;x<8;x++)
    {
        printf("                ");
        for(y=0;y<8;y++)
        {
             
            printf(" %c ",matrix[x][y]);
        }
     
    printf("\n");       
    }
    printf("\n\n\n\n");
}
  
  
int DFS(int x,int y){
 

 
    if(matrix[x][y]=='g') // goal
    {
        return 1;
    }
      if(matrix[x][y-1] == '-' ){ //WEST
           

        
        matrix[x][y-1] = '.';
        PrintMaze();
        
        
        if(DFS(x,y-1)){
            
            matrix[x][y-1] ='.'; 
            PrintMaze();
            
            return 1;
        }
        else{
            DFS(x,y-1);
            return 0;
        
         }
         DFS(x,y-1);
      

     }
      if(matrix[x-1][y] == '-'){  //NORTH
       
   
        matrix[x-1][y] = '.';
        PrintMaze();
        
        if(DFS(x-1,y)){
            
            matrix[x-1][y] = '.';
            PrintMaze();
            
            return 1;
        }
        else{
            DFS(x-1,y);
            return 0;
        }
     
         DFS(x-1,y);
    

     }
    
    
 
    
    
    
       if(matrix[x+1][y] == '-'){ //SOUTH
             
     
        matrix[x+1][y] = '.';
        PrintMaze();
        
        if(DFS(x+1,y)){
            
           matrix[x+1][y] ='.'; 
           PrintMaze();
            
            return 1;
            
        }
        else{
          DFS(x+1,y);
            return 0;
        }
        
        DFS(x+1,y);
 
    }  
  
    
           if(matrix[x][y+1] == '-'){     //EAST
          

        matrix[x][y+1] = '.';
       
        if(DFS(x,y+1)){
            
        matrix[x][y+1] = '.'; 
        PrintMaze();
          
            return 1;
        }
        else{
            DFS(x,y+1);
            return 0;
        }
        
        DFS(x,y+1);
    
    }
    
 

    return 0;


}


void StartSearch()
{ 
    printf("                  STEP BY STEP");

    int x,y;

 
    for(x=0;x<8;x++)
    {
        for(y=0;y<8;y++)
        {
            if(matrix[x][y] == 's')//start
            {
              DFS(x,y);
 
             }
        }
        
    printf("\n");  
         
    }
 
}
 
int main()
{
    ReadFile();
    
    PrintMaze();
    
    StartSearch();
    
    PrintMaze();
    
    return 0;
}

myMaze.txt

# # # # # # # #  
# g - - # - - #       
# # # - - - # # 
# - # # - - - # 
# - - # - - - #
# - - - - # # # 
# - - # - - s #
# # # # # # # #

DFS determines direction based on first if condition inside the function.Other directions should also be considered.

Answer 1

First of all, enable and heed your compiler's warnings! (With gcc, I use -Wall -Wextra -pedantic). You were told to this already. Why come to SO when the compiler can answer your questions for you!

DFS(int i,int j) means int DFS(int i,int j), but you meant to use void DFS(int i,int j). (It's not what you need, though. You already had what you need.)

---

Next, let's identify the expected output since you're not sure. This maze has five solutions (ignoring solutions that pointlessly visit a cell twice).

Length = 9
# # # # # # # #
# g . . # - - #
# # # . . - # #
# - # # . - - #
# - - # . - - #
# - - - . # # #
# - - # . . s #
# # # # # # # #

Length = 11
# # # # # # # #        # # # # # # # #
# g . . # - - #        # g . . # - - #
# # # . . - # #        # # # . . . # #
# - # # . . - #        # - # # - . - #
# - - # . . - #        # - - # . . - #
# - - - . # # #        # - - - . # # #
# - - # . . s #        # - - # . . s #
# # # # # # # #        # # # # # # # #

Length = 13
# # # # # # # #        # # # # # # # #
# g . . # - - #        # g . . # - - #
# # # . . - # #        # # # . . . # #
# - # # . . . #        # - # # - . . #
# - - # . . . #        # - - # . . . #
# - - - . # # #        # - - - . # # #
# - - # . . s #        # - - # . . s #
# # # # # # # #        # # # # # # # #

Any of these would be a valid output. Obviously, the first path is shorter than the other two, but a DFS doesn't (necessarily) find the shortest path. (You'd want a BFS for that.)

---

On to the question.

You have two problems:

• You are marking every cell you've visited, whether it's part of the path or not.
• You never stop searching, so you end up visiting every reachable cell.

In order to solve the two problems, one important change needs to be made. DFS needs to return whether the cell identified by its parameters is part of the path or not.

DFS should return 1 if the cell is part of the path, or 0 if it isn't.

So how do you know if the cell is part of the path?

• If the current cell is g, the current cell is part of the path.
• If the cell to the North is part of the path (i.e. if DFS(y-1,x) returned a true value), the current cell is part of the path.
• If the cell to the South is part of the path (i.e. if DFS(y+1,x) returned a true value), the current cell is part of the path.
• If the cell to the West is part of the path (i.e. if DFS(y,x-1) returned a true value), the current cell is part of the path.
• If the cell to the East is part of the path (i.e. if DFS(y,x+1) returned a true value), the current cell is part of the path.
• Otherwise, the cell is not part of the path.

---

Problem #2: You keep searching after finding a solution.

As soon as you know a cell is part of the path, DFS should return. Immediately. Don't go on checking the node to the South if the cell to the North is part of the path!

---

Problem #1: You are marking every cell you've visited

When you enter DFS, you mark the cell as being part of the path by making it .. This is good as it prevents infinite loop.

But it might not end up being part of the path. As previously mentioned, you need to restore its value to - if it turns out not to be part of the path.