C program for mice in the maze - backtracking-2

The rat in the maze is also a common problem using backtracking. I

A maze is a two-dimensional matrix in which some cells are blocked. One of the cells is the source cell and we have to start from there. Another of these is the destination, the place we must get to. We have to find a path from source to destination without entering any blocked cells. A picture of the unsolved maze is shown below.

This is the solution.

To solve this puzzle, we first start from the source unit and move in the direction where the path is not blocked. If the path taken leads us to our destination, the puzzle is solved. Otherwise, we will come back and change the direction of the path we are on. We will implement the same logic in code as well.

Input:
maze[][] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}}

Output:
1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1

Explanation

First, we will make a matrix to represent the maze, the elements of the matrix will be 0 or 1. 1 means blocked cells and 0 means cells we can move. The matrix for the maze shown above is as follows:

0 1 0 1 1
0 0 0 0 0
1 0 1 0 1
0 0 1 0 0
1 0 0 1 0

Now, we will make another matrix of the same dimensions to store the solution. Its elements will also be 0 or 1. 1 will represent the cells in our path and the remaining cells will be 0. The matrix representing the solution is:

1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1

So, we now have our matrix. Next, we will find the path from the start cell to the target cell, the steps we will take are as follows:

• Check the current cell, if it is the target cell, then The puzzle is solved.

• If not, try moving down and see if you can move to the next cell (to move to a cell, it must be empty and not in the path).

• If you can move to the next cell, continue moving along the path to the next lower cell.

• If not, try moving to the right. If the right side is blocked or occupied, move up.

• Similarly, if moving up is not possible, we will simply move to the left cell.

• If movement is not possible in any of the four directions (down, right, up or left), simply go back and change the current path (backtracking).

So, to summarize, we try to move from the current cell to other cells (down, right, up and left) and if no movement is possible, return and The direction of the path is changed to another cell.

printsolution → This function simply prints the solution matrix.

solvemaze → This is the function that actually implements the backtracking algorithm. First, we check if our cell is the target cell, if so (r==SIZE-1) and (c==SIZE-1). If it's the target cell, our puzzle has been solved. If not, then we check if it is a valid mobile cell. A valid cell must be in the matrix, i.e. the index must be between 0 and SIZE-1, r>=0 && c>=0 && r

Example

#include <iostream>
using namespace std;
#define SIZE 5
//the maze problem
int maze[SIZE][SIZE] = {
   {0,1,0,1,1},
   {0,0,0,0,0},
   {1,0,1,0,1},
   {0,0,1,0,0},
   {1,0,0,1,0}
};
//matrix to store the solution
int solution[SIZE][SIZE];
//function to print the solution matrix
void printsolution() {
   int i,j;
   for(i=0;i<SIZE;i++) {
      for(j=0;j<SIZE;j++) {
         printf("%d\t",solution[i][j]);
      }
      printf("</p><p></p><p>");
   }
}
//function to solve the maze
//using backtracking
int solvemaze(int r, int c) {
   //if destination is reached, maze is solved
   //destination is the last cell(maze[SIZE-1][SIZE-1])
   if((r==SIZE-1) && (c==SIZE-1) {
      solution[r][c] = 1;
      return 1;
   }
   //checking if we can visit in this cell or not
   //the indices of the cell must be in (0,SIZE-1)
   //and solution[r][c] == 0 is making sure that the cell is not already visited
   //maze[r][c] == 0 is making sure that the cell is not blocked
   if(r>=0 && c>=0 && r<SIZE && c<SIZE && solution[r][c] == 0 && maze[r][c] == 0){
      //if safe to visit then visit the cell
      solution[r][c] = 1;
      //going down
      if(solvemaze(r+1, c))
         return 1;
      //going right
      if(solvemaze(r, c+1))
         return 1;
      //going up
      if(solvemaze(r-1, c))
         return 1;
      //going left
      if(solvemaze(r, c-1))
         return 1;
      //backtracking
      solution[r][c] = 0;
      return 0;
   }
   return 0;
}
int main() {
   //making all elements of the solution matrix 0
   int i,j;
   for(i=0; i<SIZE; i++) {
      for(j=0; j<SIZE; j++) {
         solution[i][j] = 0;
      }
   }
   if (solvemaze(0,0))
      printsolution();
   else
      printf("No solution</p><p>");
   return 0;
}

The above is the detailed content of C program for mice in the maze - backtracking-2. For more information, please follow other related articles on the PHP Chinese website!