maze

#include <stdio.h>

#define N 7
#define M 7

void printSolution(int sol[N][M], int* solutionCount) {
    printf("SOLUTION IS:\n");
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < M - 1; j++) {
            printf("%d ", sol[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    (*solutionCount)++;
}

int isSafe(int x, int y, int sol[N][M], int maze[N][M]) {
    return maze[x][y] == 0 && sol[x][y] == 0;
}

void solveMazeUtil(int x, int y, int sol[N][M], int maze[N][M], int* solutionCount) {
    if (x == N - 2 && y == M - 2) {
        sol[x][y] = 1;
        printSolution(sol, solutionCount);
        sol[x][y] = 0; // Backtrack to find more solutions
        return;
    }

    if (isSafe(x, y, sol, maze)) {
        sol[x][y] = 1;

        // Explore all four directions
        solveMazeUtil(x, y + 1, sol, maze, solutionCount);
        solveMazeUtil(x + 1, y, sol, maze, solutionCount);
        solveMazeUtil(x, y - 1, sol, maze, solutionCount);
        solveMazeUtil(x - 1, y, sol, maze, solutionCount);

        sol[x][y] = 0; // Backtrack
    }
}

void solveMaze(int maze[N][M]) {
    int sol[N][M] = {0};
    int solutionCount = 0;

    solveMazeUtil(1, 1, sol, maze, &solutionCount);

    if (solutionCount == 0) {
        printf("No solution found\n");
    } else {
        printf("Total number of solutions: %d\n", solutionCount);
    }
}

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

    // Maze with no solution
    int maze2[N][M] = {
        {1, 1, 1, 1, 1, 1, 1},
        {1, 0, 1, 0, 1, 0, 1},
        {1, 0, 1, 0, 1, 0, 1},
        {1, 0, 1, 1, 1, 0, 1},
        {1, 0, 0, 0, 1, 0, 1},
        {1, 1, 1, 1, 1, 0, 1},
        {1, 1, 1, 1, 1, 1, 1}
    };

    // Maze with one solution
    int maze3[N][M] = {
        {1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 0, 1, 0, 1},
        {1, 1, 1, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 0, 1},
        {1, 0, 1, 1, 1, 1, 1},
        {1, 0, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1}
    };

    // Another maze with one solution
    int maze4[N][M] = {
        {1, 1, 1, 1, 1, 1, 1},
        {1, 0, 1, 0, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 1},
        {1, 0, 0, 0, 1, 0, 1},
        {1, 1, 1, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1}
    };


    solveMaze(maze);
    printf("\n\n");
    solveMaze(maze2);
     printf("\n\n");
    solveMaze(maze3);
     printf("\n\n");
    solveMaze(maze4);
    return 0;
}