Learn backtracking algorithm

Question

I want to learn the backtracking algorithm. Can someone please teach me some of it? I tried learning from some websites, but it didn't work. So can someone please teach me. Thank you!

Answer 1

Though language agnostic, this tutorial is nice and presents several examples that might provide the necessary intuition.

That said, the idea behind backtracking is not difficult to grasp at all. A backtracking algorithm essentially explores all the solution space just like when performing a brute force, except (and this makes it more efficient) it backtracks from a partial solution as soon as it realizes that it is not feasible.

An example

Consider this partial solution for the well known eight queens problem.

The queens in the first four columns have already been positioned, but the the last one is in an invalid square. A brute force solution would continue placing queens for the rest of the columns, oblivious of the fact that regardless of how this partial solution is augmented the result will be invalid.

The backtracking algorithm will be "smarter": it will realize the fourth queen is incorrectly placed and "go back" to considering other squares for it.

Answer 2

Fundamentals Of Computer Algorithms contains a nice chapter on backtracking. But you have not specified how much familiar you are with formal algorithm text and data structures. You may have some problems in reading this book if you are not familiar with basic algorithmic things like complexity analysis or don't know what is a tree. I mean in that case you will need to read the book from the beginning, direct jumping to backtracking chapter will not be much helpful.