Objective:

The objective of this program is to find a path from the start point (usually top-left corner) to the exit point (usually bottom-right corner) in a given maze. The maze is represented as a 2D array where some cells are blocked (denoted by ‘1’) and some are open (denoted by ‘0’). The program will use a depth-first search technique to navigate through the maze and find a solution if possible.

Code for Maze Solver:

#include 
#include 

#define N 5 // Size of the maze (N x N)

int maze[N][N] = {
    {1, 0, 0, 0, 0},
    {1, 1, 0, 1, 0},
    {0, 1, 0, 0, 0},
    {0, 1, 1, 1, 1},
    {0, 0, 0, 0, 1}
};

bool isSafe(int maze[N][N], int x, int y) {
    // Check if (x, y) is within bounds and not blocked
    return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 0);
}

bool solveMaze(int maze[N][N], int x, int y, int solution[N][N]) {
    // Base case: If we reach the destination (bottom-right corner)
    if (x == N-1 && y == N-1) {
        solution[x][y] = 1;
        return true;
    }

    // Check if maze[x][y] is a valid move
    if (isSafe(maze, x, y)) {
        // Mark the current cell as part of the solution
        solution[x][y] = 1;

        // Move forward in the x direction
        if (solveMaze(maze, x + 1, y, solution)) {
            return true;
        }

        // If moving in x direction doesn't work, move downwards in y direction
        if (solveMaze(maze, x, y + 1, solution)) {
            return true;
        }

        // If none of the moves work, backtrack and unmark this cell
        solution[x][y] = 0;
        return false;
    }

    return false;
}

void printSolution(int solution[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", solution[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int solution[N][N] = {0};

    if (solveMaze(maze, 0, 0, solution) == false) {
        printf("No solution exists\n");
    } else {
        printf("Solution path:\n");
        printSolution(solution);
    }

    return 0;
}

Explanation of the Program Structure:

The program is structured to solve the maze using a backtracking algorithm:

• isSafe: This function checks if the current position (x, y) is within the maze bounds and not blocked.
• solveMaze: This is the core function that attempts to solve the maze using depth-first search. It marks the path, and if it reaches the destination (bottom-right corner), it returns true. If no valid path is found, it backtracks.
• printSolution: This function prints the solution path. A 1 in the solution array indicates a valid move.
• main: The main function initializes the maze and solution arrays and calls the solveMaze function to find the path.

How to Run the Program:

1. Copy and paste the code into a C file (e.g., maze_solver.c).
2. Compile the C program using a C compiler (e.g., gcc maze_solver.c -o maze_solver).
3. Run the compiled program (e.g., ./maze_solver).
4. If there is a solution, it will display the path. Otherwise, it will print “No solution exists”.