This is one of the important problem which is mostly asked in technical interviews or technical tests
Lets understand the maze problem first then we will write a C program to solve the maze problem.
Maze is a matrix of N*N which is filled with 1 or 0.In Maze problem a rat starts from (0,0) and has to reach at (n-1,n-1) which is the exit point of maze.Rat can move up, down ,left , right if there is a way to go.
Let assume we have following 4*4 matrix.
1 1 0 0
0 1 0 0
1 1 0 0
1 1 1 1
Above is the given maze matrix filled 1 or 0 . 1 indicates the allowed move and 0 indicates not allowed to move.Rat starts from (0,0) and checks the value of left,right,up and down one by one till its find the 1.Once it find the possible move it moves to that cell and go ahead one by one after checking the possible moves at each step.If at any step rat find that there is no possible move ahead and still it has not reached the exit point ,then it moves back one step and check the other alternatives and choose accordingly till its find the path to exit.
from the above maze we can see that first rat starts at (0,0) and then check for the right position which is 1.So it moves to that cell and check the right cell which is zero and then checks the down cell which is 1.So it moves to the down cell and continue till it reach the exit point. So path from starting point to exit will be
(0,0) -> (0,1) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)
As we have understand the maze problem.Lets Write the C Program to solve this.
#include<stdio.h>
#include<conio.h>
#define V 4 /*size of matrix */
int isSafe(int x,int y,int G[V][V],int Sol[V][V]) /* to check the safe move */
{
if(x>=0 && x<V && y>=0&&y<V && G[x][y]==1 && !Sol[x][y])
return 1;
else
return 0;
}
int MazeRecur(int G[V][V], int Sol[V][V], int x,int y) /* checking for the path to our exit point */
{
if(x==V-1 &&y==V-1)
{
Sol[x][y]=1;
return 1;
}
if(isSafe(x,y,G,Sol)==1)
{ Sol[x][y]=1;
if(MazeRecur(G,Sol,x,y+1)==1) /* right move possible */
return 1;
if(MazeRecur(G,Sol,x+1,y)==1) /* down move possible */
return 1;
if(MazeRecur(G,Sol,x,y-1)==1) /* left move possible */
return 1;
if(MazeRecur(G,Sol,x-1,y)==1) /* up move possible */
return 1;
Sol[x][y]=0;
}
return 0;
}
int main()
{
clrscr();
int G[V][V]={{1,1,0,0}, /* initialize the maze matrix */
{0,1,0,0},
{1,1,0,0},
{1,1,1,1}};
int sol[V][V] = {0};
if(MazeRecur(G,sol,0,0)==1)
{
printf("Solution Exists\n");
for(int i=0; i<V;i++)
{
for(int j=0; j<V; j++)
printf("%d\t",sol[i][j]);
printf("\n");
}
}
else
printf("No Solution Exists");
getch();
return 0;
}
If you have any queries feel free to ask me............. :)
