Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.
Pseudo code for backtracking algorithm
Pick a starting point.
while(Problem is not solved)
For each path from the starting point.
check if selected path is safe, if yes select it
and make recursive call to rest of the problem
before which undo the current move.
End For
If none of the move works out, return false, NO SOLUTON.
From :
Backtracking is a form of recursion.
The usual scenario is that you are faced with a number of options, and you must choose one of these. After you make your choice you will get a new set of options; just what set of options you get depends on what choice you made. This procedure is repeated over and over until you reach a final state. If you made a good sequence of choices, your final state is agoal state;if you didn't, it isn't.
From Harvard FAS Computer Science S-111:
Recursion Revisited; Recursive Backtracking
Template for Recursive Backtracking
// n is the number of the variable that the current
// call of the method is responsible for
boolean findSolution(int n, possibly other params) {
if (found a solution) {
this.displaySolution();
return true;
}
// loop over possible values for the nth variable
for (val = first to last) {
if (this.isValid(val, n)) {
this.applyValue(val, n);
if (this.findSolution(n + 1, other params)) {
return true;
}
this.removeValue(val, n);
}
}
return false;
}
Template for Finding Multiple Solutions (up to some target number of solutions)
boolean findSolutions(int n, possibly other params) {
if (found a solution) {
this.displaySolution();
this.solutionsFound++;
return (this.solutionsFound >= this.target);
}
// loop over possible values for the nth variable
for (val = first to last) {
if (isValid(val, n)) {
this.applyValue(val, n);
if (this.findSolutions(n + 1, other params)) {
return true;
}
this.removeValue(val, n);
}
}
return false;
}