Maze Solver in C
Maze is a two-dimensional grid. It has the values of 0’s and 1’s. maze solving is the process of finding the path from two entries. This implementation uses Depth-First-Search to find the path.
C implementation:
Let us create a Maze as two dimensional array. Here, value ‘1’
represents path and ‘0’ represents wall(no path).
- The path starts from top-left and travels through bottom-right.
- ‘isitSafe()’ function checks the path is available or not.
- ‘solve_maze()’ finds the solution for this maze solver.
- ‘displaysolution()’ prints the solved maze.
- ‘main()’ calls the function ‘solve_maze()’ and prints the value according to it.
C Program:
#include <stdio.h>
#define no 5
int maze[no][no] = {
{1, 1, 0, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 0, 0, 1}
};
int m_soln[no][no];
int isitSafe(int x, int y) {
return (x >= 0
&& x < no && y >= 0 && y < no &&
maze[x][y] == 1);
}
int solve_Maze(int x, int y) {
if (x == no - 1
&& y == no - 1) {
m_soln[x][y] =
1;
return 1;
}
if (isitSafe(x,
y)) {
m_soln[x][y] =
1;
// To Move in
the Right direction
if
(solve_Maze(x, y + 1)) return 1;
// To Move
Down in the Left direction
if
(solve_Maze(x + 1, y)) return 1;
// it is
Backtracking process
m_soln[x][y] =
0;
return 0;
}
return 0;
}
void displaySolution() {
for (int i = 0; i
< no; i++) {
for (int j =
0; j < no; j++)
printf("%d ", m_soln[i][j]);
printf("\n");
}
}
if
(solve_Maze(2,4))
displaySolution();
else
printf("No solution found.\n");
return 0;
}
Output:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
Thus the C program to solve a Maze was written and executed
successfully. Hope, this code will help you. Keep Coding!!!
Comments
Post a Comment