Skip to main content

backtracking

Backtracking Algorithm​

Backtracking algorithm are like problem solving strategies that help to explore differnet options to find the best solutions. They work by trying differnet paths and if one doesn't work, they backtrack and try another until they find the right one. It's like solving differnet puzzle by testing differnet pieces until they fit together perfectly.

Table of contents​

  • What is backtracking?
  • How Does a Backtracking Work?
  • Example of Backtracking Algorithm
  • When to use a BAcktracking Algorithm?
  • Applications of Backtracking Algorithm
  • BAsics of Backtracking Algorithm
  • Stndard Problems of Backtracking Algorithm
  • Easy problems on Bactracking Algorithm
  • Meduim Probles onBacktracking Algorithm

What is Bactracking Algorithm?​

Backtracking is problem solving algorithm technique that invloves finding a silution incremently by trying differnet options and undoing them if they lead to dead end.

It is commnaly used in situtations where you need to explore multiple possiblities to solve a problem, like searching for a path in a maze or solving Sudoko. When a dead end reached, the algorithm backtracks to the previous decision point and explorers a differnet path until a solution is found or all possibilities have been exhausted.

How does a Backtracking Algorithm Work?​

A Backtracking algorithm works by recursively exploring all possible solutions to a problem. It starts by choosing an initial solution, and then it explores all possible extensions of that solution. If an extension leads to a solution, the algorithm reurns that solution. If an extension leads to a solution, The algorithm retuns that solution. If an extension does not lead to a solution, the algorithm backtracks the previous solution and tries a differnet extension.

The following is a outline of how a backtracking algorithm works.

  1. Choose an intial soution.
  2. Explorer all possible extesnions of current solution.
  3. If an extension leads to a solution, return that solution.
  4. If no solution found for that extension, return back to inital solution and restart new extension.
  5. Repeat steps 2 to 4 untils all possible solution have been explored.

Example of backtracking Algorithm​

Example: Finding the shortest path through a maze Input: A maze repesetnetd as a 2D array, where 0 represents an open space and 1 represents a wall.

Algorithms:

  1. Start at the starting point.
  2. For each of the possible directions (up, down, left, right) try moving in that direction.
  3. If the moving in that direction leads to the ending point, return the path taken.
  4. If moving in the direction does not lead to the ending point, backtrack to the previus position and try a different direction.
  5. Repeat 2-4 until the ending point is reached or all possible path have been explored

Reference - https://www.geeksforgeeks.org/backtracking-algorithms