Learn backtracking algorithm

Question

I want to learn the reverse tracking algorithm. Can someone please teach me this? I tried to study on some sites, but it did not work. So someone can teach me. Thanks!

Answer 1

Although the language is agnostic, this tutorial is good and presents several examples that can provide the necessary intuition.

However, the idea of ​​lagging is by no means difficult to understand. The backtracking algorithm essentially explores the entire solution space except in the case of brute force execution, except (and this makes it more efficient), it departs from the partial solution as soon as it understands that this is impossible.

Example

Consider this partial solution to the well-known eight queen problem.

Farmers in the first four columns are already positioned, but the latter has an invalid square. A brute force decision would continue to place the queens for the remaining columns, not paying attention to the fact that no matter how this partial decision is supplemented, the result will be invalid.

The backtracking algorithm will be “smarter”: he will understand that the fourth queen is incorrectly placed and will “return” to the consideration of other squares for her.

Answer 2

The basics of computer algorithms contains a good chapter on going back. But you did not indicate how familiar you are with formal text and data structures. You may have trouble reading this book if you are not familiar with basic algorithmic things, such as complexity analysis, or do not know what a tree is. I mean, in this case, you will need to read the book from the very beginning, a direct retelling of the return chapter will not be very useful.