Maze Algorithm.

Problem Statement: A mouse is at one corner of a maze and he has to reach the corner diagonally opposite to him. Write an algorithm to find the path through the maze. The maze is represented by a matrix of '0's and '1's where '1' denotes a path and '0' denotes a wall.

This problem can be solved using backtracking. Below is the code,

#define N 4

void printMaze(int maze[N][N])
{
    int i, j;

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

void move(int maze[N][N], int sol[N][N], int x, int y)
{
    if((x == N-1) && (y == N-1))
    {
        sol[x][y] = 1;
        printMaze(sol);
        return;
    }

    if(x != N-1)
    {
        if(maze[x+1][y])
        {
            sol[x][y] = 1;
            move(maze, sol, x+1, y);
            sol[x][y] = 0;
        }
    }

    if(y != N-1)
    {
        if(maze[x][y+1])
        {
            sol[x][y] = 1;
            move(maze, sol, x, y+1);
            sol[x][y] = 0;
        }
    }
}

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

    int sol[N][N] = {0,};

    move(maze, sol, 0, 0);
    return 0;
}