I was trying to solve this maze with the following code. But the answers aren't accurate for all inputs like n=4

Question

Maze problem

You are provided a matrix of size N*N with source position at (0,0) and destination at (N-1,N-1) in a 2D array. Some of the positions in the array are marked as 0 which are blocked cells, rest being marked 1.

A path is a connected sequence of elements from (0,0) to (N-1,N-1) which consists of 1. A sequence of 1s in the 2D array is connected if every 1 in the sequence is adjacent (the above or left neighbour) to the next 1 in the sequence.

For example, in the following matrix,

1 1 0
0 1 1
1 0 1 

the 1s marked in blue is a connected path from (0,0) to (2,2)

Note that cells at (0,0) and (N-1,N-1) are always 1. You can either make movement towards right or down, i.e., from position (x,y), you can go to either the position (x,y+1) or (x+1,y).

Input

First line consists of the size of the input array N (<=50), following that would be the state of NxN maze which would consist of 0s and 1s.

Output

You have to print "POSSIBLE" if there exists a path between the source and the destination otherwise print "NOT POSSIBLE".

Problematic cases

For the following input,

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

The console displays NOT POSSIBLE whereas the correct output should be POSSIBLE.

C Code

#include<stdio.h>

#define true 1
#define false 0
// Maze size
int N;

int solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);

/* A utility function to print solution matrix sol[N][N] */
void printSolution(int sol[N][N])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            printf(" %d ", sol[i][j]);
        printf("\n");
    }
}

/* A utility function to check if x,y is valid index for N*N maze */
int isSafe(int maze[N][N], int x, int y)
{
    // if (x,y outside maze) return false
    if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
        return true;

    return false;
}

/* This function solves the Maze problem using Backtracking.  It mainly uses
solveMazeUtil() to solve the problem. It returns false if no path is possible,
otherwise return true and prints the path in the form of 1s. Please note that
there may be more than one solutions, this function prints one of the feasible
solutions.*/
int solveMaze(int maze[N][N])
{
    int sol[N][N] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };

    if(solveMazeUtil(maze, 0, 0, sol) == false)
    {
        printf("NOT POSSIBLE");
        return false;
    }
printf("POSSIBLE");
   // printSolution(sol);
    return true;
}

/* A recursive utility function to solve Maze problem */
int solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
    // if (x,y is goal) return true
    if(x == N-1 && y == N-1)
    {
        sol[x][y] = 1;
        return true;
    }

    // Check if maze[x][y] is valid
    if(isSafe(maze, x, y) == true)
    {
        // mark x,y as part of solution path
        sol[x][y] = 1;

        /* Move forward in x direction */
        if (solveMazeUtil(maze, x+1, y, sol) == true)
            return true;

        /* If moving in x direction doesn't give solution then
           Move down in y direction  */
        if (solveMazeUtil(maze, x, y+1, sol) == true)
            return true;

        /* If none of the above movements work then BACKTRACK: 
            unmark x,y as part of solution path */
        sol[x][y] = 0;
        return false;
    }   

    return false;
}

// driver program to test above function
int main()
{
    int n;
    scanf("%d",&n);
    N=n;
    int maze[52][52]  ;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            scanf("%d",&maze[i][j]);
        }
    solveMaze(maze);
    return 0;
}

Answer 1

With the change to make N be a variable, your code is nearly correct. You just overlooked one place where you had hardcoded 52 instead of N:

int maze[52][52]; should be int maze[N][N];

Another thing, which your compiler should have warned you about, is that the line:

int sol[N][N] = {  // etc.

is not allowed: variable-length arrays may not have initializers. You will need to initialize either via a loop or via memset (which needs #include <string.h>):

int sol[N][N];
memset(&sol, 0, sizeof sol);

After making these changes, your code works for me on some simple mazes.

---

There is a different issue too; your maze solving algorithm can't cope with mazes where you have to go down then up (or right then left). So it works for any 4x4 maze but it fails for this maze:

5
1 0 1 1 1
1 0 1 0 1
1 0 1 0 1
1 1 1 0 1
0 0 0 0 1

However, your problem description seems to define that the path should only ever move right or down. So, subject to that condition, your code will be able to solve all the required mazes. Perhaps as an extra exercise you could update your code to be able to solve mazes like this one I have just posted :)

Answer 2

This is a very interesting problem where dynamic-programming comes handy. In fact this is the example that I use whenever someone asks me what is dynamic programming.

Now here are the questions that are worth considering:

If a cell is 0, is it still possible to reach this cell?

If a cell is 1, how would you know that you could reach this cell? What are the different ways that you could use to get to this cell?

The first question is obvious. If a cell is 0 then it cannot be reached.

The second question is less so, but still quite straightforward: a cell can be reached in two ways: from the cell above it or the cell to its left.

Now that we have made these observation, we know that given the last cell (N-1, N-1), we know that it can be reached if:

1. the cell is 1 &&
2. the cell above or the cell to its left can be reached.

Recursively, we could eventually find out if there is such a path by recursively call the two cells if the current cell is 1.

---

Now, that's not very efficient. In the worst case where all cells are 1, the complexity is exponential. How can we do better?

What about the first column and first row of the maze? When can they be reached?

Cells in the first row/column can only be reached in one way (imagine row -1 and col -1 are filled with 0) and as we know the cell (0,0) is 1, we can iteratively find out the reachability of all the cells in the first row/col. With first row/col, you could do the same for the second row/col!

In other words, the states of one row depends on the row above it; the states of one column depends on the column to its left. We already have the row/col -1 by definition, the rest can be computed iteratively, row by row, in O(n^2).

I intentionally did not provide the code as the thought process is probably more valuable here. Hope that helps!