I have a good basic understanding of the fundamentals of C++, I also have an understanding of how recursion works too. I came across certain problems like the classic eight queens problem and solving a Sudoku with Backtracking.
I realize that I'm quite lost when it comes to this, I can't seem to be able to get my mind around the concept of going back in the recursion stack and starting again in order to solve the problem. It seems easy with a pen and paper but when it comes to writing code for this, I'm confused on how to begin attacking these problems.
It would be helpful if there were a tutorial aimed at beginners to backtracking or if there were a good book where this was covered. If somebody can shed light on this topic or give me some links to decent references, I'd be really grateful.
And yes I do know that it would be easier in functional languages but I'd like to understand the implementation in imperative languages too.
Best Answer
In backtracking, you are not starting again. Instead, you iterate through all options at the current situation.
Think about finding solution for a maze. At one point where you have two different paths, you try the left one first. If the left one does not lead you to the exit, you return to the point and try the other path. That's how backtracking works. In 8 Q and other problems where backtracking can be used, the confusing part is in the problem domain - how to iterate through your options in a given situation in a deterministic way.
EDIT: the following is a pseudo code helping understanding backtracking.
For 8Q question: