What is the standard backtracking template, and what are its parts?
The template has four parts, and they are always in the same order. The state, the stopping condition, the loop over the choices, and the undo at the end.
def search(state, remaining):
if remaining == 0:
record(state)
return
for choice in choices:
if not allowed(state, choice):
continue
search(state + choice, remaining - 1)
undo(choice)
So let us take the parts one at a time.
The first part is the state. That is the information the function needs to carry with it, and it usually comes in two pieces. What has been chosen so far, and what is still needed. In the template above, state is what has been chosen and remaining is what is left.
The second part is the stopping condition. It says when the answer is complete, and it also says when there is no point in going on. There are two reasons to stop, and they are different. The first is that the answer is finished, so you record it and you return. The second is that the state is broken, so you return without recording anything.
The third part is the loop over the choices. Every choice is tried in turn, and the check inside the loop throws away the ones that cannot work. That check is where the pruning goes, and it is the thing that makes the search fast.
The fourth part is the undo. You put the choice into the state, you call yourself, and then you take it back out. The undo has to happen whether the call succeeded or failed, so it goes after the call and not inside it.
the part what it does
------------------- --------------------------------------------
the state carries what has been chosen and what is left
the stopping case the answer is complete, or the state is broken
the loop tries each choice in turn
the check throws away the choices that cannot work
the undo puts the state back the way it was
And there are two details that people get wrong. The first one is forgetting the undo, which makes every later answer wrong because the state has rubbish left in it. The second one is putting the undo inside an if that only runs when the call fails, so the state is not put back on the successful path.
So the rule to remember is this. Record when it is finished, try every choice, and always undo.
The next two questions in this topic show the template on two real problems.