Skip to main content

Ant in a Maze problem

Ant in a maze is another problem that can be solved using backtracking algorithm.In this problem there is a NxN  maze in which one corner of maze is entry point and other is exit point.Now there is an ant in a maze who wants to go from entry to exit.For doing this there are certain constraints like an ant can move only forward or downward but no backward and upward.For the sake of simplicity we are taking 4x4 Maze.The maze can be denoted by a matrix with values 0 and 1.0 means the path is blocked and 1 means the path is available.The maze and the path for ant from entry to exit is


The block which are in grey color are dead end in the maze that is the ant cannot go through such blocks.The red path is the path travelled by ant from entry to exit.The matrix representation of the above maze without the path will be (input to be taken)

maze[4][4]={{1,1,0,0},
{1,1,0,1},
{0,1,0,0},
{1,1,1,1}
}

and the matrix representation of path travelled by ant will be (output to be displayed)

Path[4][4]={{1,1,0,0},
{0,1,0,0},
{0,1,0,0},
{0,1,1,1}
}

Algorithm :

1) Mark current block in a matrix as 1
2) Move horizontally in forward direction and recursively check whether this leads to solution.
3) If the above step doesn't lead to the valid solution then move downwards and check whether this leads to the solution.
4) If none of the above solutions work then unmark the block as 0 and return false.

Program :

#include<stdio.h>
#include<conio.h>


bool Findpath(int maze[4][4], int x, int y, int Path[4][4])
{
    
    if(x == 3 && y == 3)           //Exit point is reached
    {
        Path[x][y] = 1;
        return true;
    }

   
    if(isvalid(maze, x, y) == true)     // Check if maze[x][y] is valid
    {
        
        Path[x][y] = 1;                        // mark x,y as part of solution

        
        if (Findpath(maze, x+1, y, Path) == true)     // Move forward in x direction
            return true;

        
           
        if (Findpath(maze, x, y+1, Path) == true)     // If moving in x direction doesn't give solution Move down 
            return true;

         
            
        Path[x][y] = 0;     // If the above steps didn't work then Backtrack that is unmark x,y as part of solution
        return false;
    }   
 printpath(Path);
    return false;
}


bool isvalid(int maze[4][4], int x, int y)
{
   
    if(x >= 0 && x < 4 && y >= 0 && y < 4)             // if x,y is inside maze then return true
{  
   if(maze[x][y]==1)
        return true;
 }
    return false;
}

void printpath(int Path[4][4])
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
            printf(" %d ", Path[i][j]);
        printf("\n");
    }
}

int main()
{
    int maze[4][4]  =  { {1, 1, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {1, 1, 1, 1}
    };


    int Path[4][4] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };
    bool a=Findpath(maze,0,0,Path);
   if(a==false)
{
 printf("Solution doesnot Exist\n");
return false;
}
    getch();
}


Labels:

Comments

Post a Comment

Popular posts from this blog

Tricky Questions or Puzzles in C ( Updated for 2026)

Updated for 2026 This article was originally written when C/C++ puzzles were commonly asked in interviews. While such language-specific puzzles are less frequent today, the problem-solving and logical reasoning skills tested here remain highly relevant for modern Software Engineering, Data Engineering, SQL, and system design interviews . Why These Puzzles Still Matter in 2026 Although most Software &   Data Engineering interviews today focus on Programming, SQL, data pipelines, cloud platforms, and system design , interviewers still care deeply about how you think . These puzzles test: Logical reasoning Edge-case handling Understanding of execution flow Ability to reason under pressure The language may change , but the thinking patterns do not . How These Skills Apply to Data Engineering Interviews The same skills tested by C/C++ puzzles appear in modern interviews as: SQL edge cases and NULL handling Data pipeline failure scenarios Incremental vs ...
23 comments
Read more

Decorators in Python

Decorators provide additional functionality to the functions without directly changing their definition of them. Basically, it takes the functions as an argument, adds functionality to them, and returns it.  Before diving deep into the concept of Decorators, let's first try to understand  What are functions in Python and what is an inner function? In Python everything is Objects, be it Class, Variables, and Functions . So functions are python first-class objects that can be used or passed as an argument. You can store the functions in variables, you can pass a function to another function as parameters, and you can also return the function from the function. Below is one simple example where we are treating functions as objects . def make_me_lowercase ( str ): return str .lower() print (make_me_lowercase( "HELLO World" )) copy_of_you = make_me_lowercase print (copy_of_you( "HELLO World" )) The output of the above calls for both the functio...
2 comments
Read more

Program to uncompress a string ie a2b3c4 to aabbbcccc

Below is the program to uncompress a string #include<stdio.h> #include<conio.h> #include<stdlib.h> int main() { char str[100]="a2b3c4d8u7"; for(int i=0;str[i]!='\0';i++) { if(i%2!=0) { for(int j=0;j<atoi(&str[i]);j++) { printf("%c",str[i-1]); } } } getch(); } Want to become a Data Engineer? Check out below blog posts  1.  5 Key Skills Every Data Engineer needs in 2023 2.  How to prepare for Data Engineering Interviews 3.  Top 25 Data Engineer Questions
2 comments
Read more