Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
I think this is a good question, but I think it'd be better to emphasize the request for someone to explain backtracking over asking for tutorials or other resources. An in-depth explanation kind of answer beats a list of references any day. –  Anna Lear Jun 28 '11 at 21:42
    
It would be perfect if somebody could give a detailed explanation, but i wouldn't mind reading up references either. Its just that I don't know where to start from. –  nikhil Jun 28 '11 at 21:55
add comment

2 Answers

up vote 7 down vote accepted

... 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.

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.

# depending on the problem, backtracking is not necessarily calling the
# method itself directly. for now, let's just stick with the simple case.

def backtracking(state)
  option_list = state.get_all_options
  option_list.each {|option|
    state.apply option
    return resolved if state.is_resolved
    return resolved if backtracking(state) == resolved
    state.undo option
  }
  return not_resolved
end

For 8Q question:

  • state.get_all_options would return a list of the possible positions for the next queen
  • state.is_resolved would test if all queens are on the board and if they are good with each other.
  • state.apply and state.undo will modify the board to apply or undo a positioning.
share|improve this answer
    
The first recursive code I wrote (in 1984 using Pascal) for an assignment was a maze solving algorithm. –  Gerry Jun 28 '11 at 23:49
    
Know of some simple assignment where I can actually write code to get the actual feel of this stuff. –  nikhil Jun 29 '11 at 8:09
    
@nikhil: are you asking if there are some simple problem? It is better to write some pseudo code to demonstrate the generic routing of backtracking. I will try one later in a reply. –  Codism Jun 29 '11 at 15:23
    
Yes exactly, that'll be most helpful. –  nikhil Jun 29 '11 at 15:34
    
Thank you so much, I've been reading some stuff lately. Slowly but steadily my understanding is improving. –  nikhil Jul 1 '11 at 20:02
add comment

You have seen a program to walk a binary tree, right? It looks like this:

void walk(node* p){
  if (p == NULL) return;  // this is backtracking
  else if (WeWin(p)){
    // print We Win !!
    // do a Throw, or otherwise quit
  }
  else {
    walk(p->left);   // first try moving to the left
    walk(p->right);  // if we didn't win, try moving to the right
                     // if we still didn't win, just return (i.e. backtrack)
  }
}

There's your backtracking.

You don't actually need a physical tree. All you need is a way to make a move and later undo it, or tell if you've won, or tell if you can't go any further.

share|improve this answer
1  
can't you return a bool/int to check if the solution is found in the subtree? else{return walk(p->left)||walk(p->right));} no need for throw for the expected result –  ratchet freak Jun 28 '11 at 22:30
    
@ratchet: Absolutely. That's also a perfectly good way to do it. (I was just trying to de-clutter the example. I would actually do it your way.) –  Mike Dunlavey Jun 29 '11 at 12:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.