 In Progress
Lesson 36 of 43
In Progress

# General Method

Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree).

Backtracking algorithm is applied to some specific types of problems,

• Decision problem used to find a feasible solution of the problem.
• Optimisation problem used to find the best solution that can be applied.
• Enumeration problem used to find the set of all feasible solutions of the problem.

In backtracking problem, the algorithm tries to find a sequence path to the solution which has some small checkpoints from where the problem can backtrack if no feasible solution is found for the problem.

Example,

Here,

Green is the start point, blue is the intermediate point, red are points with no feasible solution, dark green is end solution.

Here, when the algorithm propagates to an end to check if it is a solution or not, if it is then returns the solution otherwise backtracks to the point one step behind it to find track to the next point to find solution.

## Algorithm

```Step 1 − if current_position is goal, return success
Step 2 − else,
Step 3 − if current_position is an end point, return failed.
Step 4 − else, if current_position is not end point, explore and repeat above steps.```