Backtracking


A backtracking algorithm is a problem-solving method that finds the intended output via a brute-force approach.

Backtracking implies that if the current answer isn't working, you should go back and try something else. As a result, recursion is used in this method.

When there are several solutions to a problem, this method is utilized to solve it. Dynamic programming is the way to go if you want the best result.

Tree of States in Space

A space state tree is a tree that depicts all of the problem's conceivable states (solution or nonsolution) from the root to the leaf.

Example Backtracking approach

Problem: You want to figure out all the different ways you can arrange two lads and one girl on three benches using the backtracking approach. The girl must not sit in the middle of the bench.

Solution: There are 3! = 6 choices in all. We'll investigate all options and come up with the best answer. We attempt all of the options in a recursive fashion.

Applications of Backtracking Algorithms

  • The goal is to find all Hamiltonian Paths in a graph.
  • To find a solution to the N Queen problem.
  • There is a maze puzzle to solve.
  • The issue with the Knight's tour.