Backtracking Algorithm

In this tutorial, you will learn what a backtracking algorithm is. Likewise, you will discover an illustration of a backtracking approach.

Backtracking is an algorithmic-strategy to tackle an issue in an extra way. It uses a recursive way to deal with clarify the issues. We can say that backtracking is needed to track down all conceivable combinations to tackle an optimization issue.

A backtracking algorithm is a problem-solving algorithm that uses a brute force approach for tracking down the desired output.

The Brute force approach evaluates every one of the potential solutions and picks the desired/best solutions.

The term backtracking proposes that assuming the current solution isn’t suitable, then backtrack and attempt different solutions. Along these lines, recursion is used in this methodology.

This methodology is used to tackle issues that have different solutions. In the event that you need an optimal solution, you should go for dynamic programming.

In this article, you will learn-

1 State Space Tree
2 Backtracking Algorithm
3 Example Backtracking Approach
4 Backtracking Algorithm Applications

State Space Tree

A space state tree is a tree addressing every one of the potential states (solution or nonsolution) of the issue from the root as an underlying state to the leaf as a terminal state.

Backtrack(x)
    if x is not a solution
        return false
    if x is a new solution
        add to list of solutions
    backtrack(expand x)

Example Backtracking Approach

Issue: You need to track down every one of the potential methods of arranging 2 boys and 1 girl on 3 benches. Constraint: Girl ought not be on the middle bench.

Solution: There are a total of 3! = 6 possibilities. We will attempt every one of the possibilities and get the potential solutions. We recursively attempt every one of the possibilities.

All the possibilities are:

The following state space tree shows the possible solutions.

Backtracking Algorithm Applications

To find all Hamiltonian Paths present in a graph.
To solve the N Queen problem.
Maze solving problem.
The Knight’s tour problem.

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.