1
$\begingroup$

The problem I am working on is specifically this:

A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source and has to reach the destination. The rat can move only in two directions: forward and down.

The question essentially asks to find and print the path that exists through a given maze from the top left to the bottom right of the maze. The details of the problem can be found here.

The core of the C/C++ code for this problem's solution is this:

/* A utility function to check if x,  
y is valid index for N*N maze */
bool 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.*/
bool 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("Solution doesn't exist"); 
        return false; 
    } 
  
    printSolution(sol); 
    return true; 
} 
  
/* A recursive utility function  
to solve Maze problem */
bool 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 
        && maze[x][y] == 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; 
} 

I am confused about the following part of the solution in the function solveMazeUtil:

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

What is the need to reset the value of the cell located at x,y in the solution matrix? The value of sol[x][y] was set to 1 only because it was a valid cell to go to. I don't understand why sol[x][y] has to be reset just because its neighboring cells are invalid?

EDIT:

I thought about this problem a little more and I realized the cell is only reset to zero when the program runs into a dead-end (0s in the maze, in this case) on its right side AND below it. If this cell is reset, the cell is available to be explored again. What purpose does it serve? If the program encounters this reset cell again, it will perform the same computations for this cell again and encounter the same dead-ends as before.

$\endgroup$

1 Answer 1

3
$\begingroup$

Your question title doesn't match your question details. You're not asking why backtracking is necessary, but you're asking why a cell marked in the matrix needs to be unmarked when backtracking.

A general technique for solving questions like this is as follows.

We'll investigate statements about the state of the program. In this case, statements about the contents of the matrix.

We start by looking at the intended outcome: the required postcondition. A postcondition is a statement that must always hold after the program terminates. In this case: what is the matrix supposed to contain after the program terminates?

The answer: the cells of the matrix must mark a path found from start to finish, if such a path exists. All cells marked 0 must be off that path, and all cells marked 1 must be on it.

Then, we figure out which invariant the program maintains in order to achieve the required postcondition. An invariant is a property that always holds: before, while, and after the program runs. In this case: which cells are supposed to be marked 1 while the program is in progress?

The answer: they are exactly the cells of the path found from the starting point to the current cell. If the program always successfully maintains this invariant, the required postcondition will always be met.

To maintain the invariant, when you add a cell to the path, it must be marked; and when you retrace a step, removing the last cell from the current path, that cell must be unmarked.

What if we don't unmark it? Then, the program will maintain a different invariant: namely, the matrix will mark exactly those cells that have ever been visited, whether they are on the current path or not. This is the invariant Hansel was trying to maintain with his breadcrumbs.

If you follow Hansel, after the program terminates, all cells ever visited will be marked, even those that aren't on the path that was eventually found (and such cells will exist if any backtracking occurred). The requirement was for only the cells on the path to be marked. Backtracking can actually occur, so the program will no longer always be doing what it's supposed to do: it will no longer meet its required postcondition.

$\endgroup$
11
  • $\begingroup$ Thank you very much for the elaborate answer and excuse me for the late response. $\endgroup$
    – a_sid
    Jan 1, 2021 at 9:33
  • $\begingroup$ I guess this statement of yours essentially answers my question: If you follow Hansel, after the program terminates, all cells ever visited will be marked, even those that aren't on the path that was eventually found (and such cells will exist if any backtracking occurred). The requirement was for only the cells on the path to be marked. $\endgroup$
    – a_sid
    Jan 1, 2021 at 9:34
  • $\begingroup$ I am confused by this statement: Backtracking can actually occur, so the program will no longer always be doing what it's supposed to do: it will no longer meet its required postcondition. Could you please explain it more? Do you mean to say here that backtracking is necessary in order to meet the postcondition? $\endgroup$
    – a_sid
    Jan 1, 2021 at 9:37
  • $\begingroup$ No, I mean that the postcondition is only still being satisfied when no backtracking occurs, so if there were no cases in which backtracking occurred, it would not be an issue - but there are (many) such cases, and hence the postcondition will not always be satisfied. $\endgroup$ Jan 4, 2021 at 11:51
  • $\begingroup$ ...so if there were no cases in which backtracking occurred, it would not be an issue... Isn't the postcondition that all cells on the path should be marked with a 1 and the one's that aren't should be marked with a 0? If this is the postcondition and no backtracking was taking place, then even those cells that are not on the path may be marked with a 1. Doesn't this violate the postcondition? $\endgroup$
    – a_sid
    Jan 4, 2021 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.