Concept
Definition:
Backtracking is a common technique used in computer programming to solve problems by exploring all possible solutions to a given problem and then choosing the best one. It is often used in situations where a problem has multiple solutions and it is not clear which one is the best.
General backtracking algorithm
if the current point is a feasible solution, return success.
else if all paths are exhausted (i.e current point is an endpoint), return failure, since we have no feasible solution.
else if the current point is not an endpoint, backtrack and explore other points and repeat the above steps.
One common example of backtracking is the use of the depth-first search algorithm in the tree traversal. In this algorithm, the algorithm starts at the root of the tree and explores as far as possible along each branch before backtracking and trying a different path. This allows the algorithm to quickly find a solution to the problem by quickly exploring all possibilities.
For example, suppose we are trying to solve a maze by finding the shortest path from the start to the finish. We could use a backtracking approach to this problem by breaking it down into smaller subproblems, such as finding the shortest path from the current position to the next intersection, and then to the next intersection after that, and so on. However, if we reach a dead end, we must backtrack and try a different path. This would look something like this:
function solveMaze(maze, currentPosition, destination):
if (currentPosition == destination):
return true
mark currentPosition as visited
for each possible move from currentPosition:
if move is valid:
if (solveMaze(maze, newPosition, destination) == true):
return true
unmark currentPosition
return false
Program Explanation:
Create a function that takes in the maze, the current position, and the destination as parameters.
Check if the current position is equal to the destination. If it is, return true to indicate that a path has been found.
Mark the current position as visited.
Check all possible moves from the current position (up, down, left, and right). If the move is valid (i.e. within the bounds of the maze and not a wall), then recursively call the function with the new position as the current position. If the recursive call returns true, then return true to indicate that a path has been found.
If none of the moves is successful, unmark the current position and return false to indicate that no path has been found.
Recursion Vs Backtracking
Backtracking uses recursion to solve the problem i.e All backtracking are recursion but not all recursions are backtracking.
Backtracking essentially means try out all possible combinations.
Factorial is technically not backtracking because there is only one path.
Rat maze is backtracking:
https://www.geeksforgeeks.org/rat-in-a-maze-backtracking-2/Backtracking is given as the first brute-force solution for many problems.
Note: Most important thing in backtracking is to be able to identify the state and think about the choices eg: Take, do not take etc.
So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.
Thank you, Have a nice day !!