What is backtracking in programming? When and why should we use it?

Question

I saw n queens problem and tried to solve it my way, when i couldn't solve it i saw the solution which used some backtracking algorithm. But i can not comprehend the idea behind using it and in what kind of situation is it best to use. If anyone could please provide some personal knowledge about this.

Answer 1

The best example of backtracking is when solving a maze.When we try to solve this maze many times we get stuck. So what we do ? We go backwards and find another way to reach solution.

Answer 2

For example the n queens problem:
You set the first queen, the second, then the third. Maybe you don't find a place for the third. You don't start at the beginnig, you go only one step back. Means you search another place for the second queen and try to place the third.

More generally, you try a way out, remember this approach. If you get stuck you go back to the place where it is theoretically still possible to find a solution.
This prevents you from having to try all possibilities (brute force).

A maze, n-queens-problem, a sudoku solver ... there are a lot of examples where you can use a backtracking algorithm.

Answer 3

Simply it is going through all the paths of the problem and finding the best solution

https://www.google.com/amp/s/www.geeksforgeeks.org/backtracking-introduction/amp/