In the following project, the concept of backtracking is used to solve a rat's problem in a maze using the C++ programming language.
What is Backtracking?
A BRUTE FORCE APPROACH is made in use in problems related to the backtracking algorithm.
In the brute force approach, all the possible outcomes are checked and the best of all is selected as the final result.
Backtracking suggests that if the current solution is not suitable, then backtrack (or go back) and try other solutions. This concept is used when there are multiple solutions. Dynamic programming is used for an optimal solution.
One of the most popular problems where backtracking is used is RAT IN MAZE.
The problem says that we need to find out the best path for the rat to reach from one end of the maze to the other. The maze will be an MxM matrix formed of only '1' and '0', where '1' means the path is open to moving and '0' means there is a blockage in the path.
There are various ways in which the rat can move, but in the following source code, the only movement allowed for the rat is only right or downward.
In the source code, two functions are made:
1.isCorrect - the C++ function is made to check whether the path is clear to move or not. If '1' is found to be the next element of the matrix then the path is clear and the function will return true and if '0' is found then it means that the path is not clear.
2. RatinMaze - this function is made to select the best direction in which rat will move next. suppose if the rat moves downward but the next step it takes is blocked, the rat will go back to its previous location and try to search for the best path. Here, d denotes the downward move and r denotes the right move a and the search will continue till the rat reached the location of (d=m-1,r=m-1). user will define a maze in MxM matrix form (here givenmaze) which will be dynamically created using new and the output will also be an MxM matrix (here solupath) which will be the best path chosen by the rat to reach the end of the maze.
Submitted by Nidhi Vaishya (Nidhi)
Download packets of source code on Coders Packet