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.