The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Backtracking

Problem :-
Given a maze in the form of a matrix of size n x n with all elements as 0 or 1.
0 denotes safe cell & 1 denotes dangerous cell.
A rat is placed at cell ( 0, 0 ). Print a safe path ( if exists ) which rat can take to reach last cell ( n-1, n-1 ).
Constraint :- Rat can move rightwards ( R ) or downwards ( D ).
Consider a maze of size 4 x 4 as shown below :-
0  0  1  0
1  0  0  0
1  0  1
1  0  0  0
Safe Path ( RDRDDR ) is shown below :-
0  0  1  0
1  0  0  0
1  0  1
1  0  0  0

Solution :-
The solution is a matrix in which 1s are present in the cells which consitute the path that rat may use to reach the last cell. There are two options for the rat to move ( right cell or down cell ).
1 ) Suppose the rat chooses right cell and moves there ( if the cell is safe ). At this point, it checks recursively if a path exist from that cell. If there is a path, then that cell is marked as 1 and again the rat chooses either of the two possible options and repeats the same steps.
2 ) If the path doesn't exist, then rat backtracks to the previous cell ( from where to moved to the right cell ) and chooses the down cell, moves there and again checks recursively for a possible path.
If none of these options can lead to a possible solution, then the solution doesn't exist.
See the implementation below.

#include<iostream>
#define M 4
#define N 4
using namespace std;

/* print the path matrix
  '1' is present in the cell which is a part of the path
*/
void printPathMatrix(int path[M][N]) {
   int i,j;
   cout<<"\nPath in Maze :-\n";
   for (i=0;i<M;i++) {
      for (j=0;j<N;j++) {
         cout<<path[i][j]<<" ";
      }
      cout<<endl;
   }
}

// check if we can move to a particular cell
bool validCell(int maze[M][N], int r_idx, int c_idx) {
   if (r_idx < 0 || r_idx >= M) {
      // invalid M index      
      return false;
   }
   if (c_idx < 0 || c_idx >= N) {
      // inavlid N index
      return false;
   }
   if (maze[r_idx][c_idx] != 0) {
      // cannot move to this cell
      return false;
   }
   return true;
}

/* finds a path from cell (0,0) to cell (M-1,N-1) if a path exists
   (r_idx,c_idx) -> M index and N index of the cell
*/
bool findPath(int maze[M][N], int r_idx, int c_idx, int path[N][N]) {
   if ((r_idx == M-1) && (c_idx == N-1)) {
      // we have reached the last cell
      // this implies we have found a path
      path[r_idx][c_idx] = 1;
      return true;
   }
   if (validCell(maze,r_idx,c_idx)) {
      // cell is valid i.e we can move to the cell
      path[r_idx][c_idx] = 1;

      // recursively check if a path exists from the current valid (safe) cell
      // start checking from cell (r_idx+1,c_idx)
      if (findPath(maze,r_idx+1,c_idx,path)) {
         return true;
      }

      // start checking from cell (r_idx,c_idx+1)
      if (findPath(maze,r_idx,c_idx+1,path)) {
         return true;
      }
      path[r_idx][c_idx] = 0;
      return false;
   }
}

// wrapper function
void pathInMaze(int maze[M][N]) {
   int path[N][N];
   int i,j;

   // initialize path matrix
   for (i=0;i<M;i++) {
      for (j=0;j<N;j++) {
         path[i][j] = 0;
      }
   }

   // find the path if available
   if (findPath(maze,0,0,path)) {
      cout<<"\nPath exists ...\n";
      printPathMatrix(path);
   }
   else {
      cout<<"\nPath doesn't exist ...\n";
   }
}

// main
int main() {
   int maze[M][N] = {{ 0,0,1,0 },
                     { 1,0,0,0 },
                     { 0,1,0,1 },
                     { 1,0,0,0 }};
   // 1s in the maze denotes barriers (dangerous cells),
   // we cannot move to those cells 
   pathInMaze(maze);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Backtracking technique
* Given a maze in the form of a matrix of size n x n. A robot is placed at cell ( 0, 0 ). Print all possible paths that robot can take to reach the last cell ( n-1, n-1 ) of the maze
* Given a maze in the form of a matrix of size n x n with all elements as 0 or 1. 0 denotes safe cell & 1 denotes dangerous cell. A rat is placed at cell ( 0, 0 ). Print a safe path ( if exists ) which rat can take to reach last cell ( n-1, n-1 ).
* Solve the Knight's Tour problem
* Solve the N-Queens problem
* Given a set of candidate values in an array & a target x, find all possible ways in which candidate values can be added to get x. We can use each candidate value any number of times