Steven Skiena's "Algorithm Design Manual" has the following code for the backtracking algorithm:
#include "backtrack.h"
#include "bool.h"
bool finished = FALSE; /* found all solutions yet? */
/*
a[] is the array representing a partial solution.
k is the integer representing the current position in a[].
input is auxiliary data.
*/
backtrack(int a[], int k, data input)
{
int c[MAXCANDIDATES]; /* candidates for next position */
int ncandidates; /* next position candidate count */
int i; /* counter */
if (is_a_solution(a,k,input))
process_solution(a,k,input);
else {
k = k+1;
construct_candidates(a,k,input,c,&ncandidates);
for (i=0; i<ncandidates; i++) {
a[k] = c[i];
make_move(a,k,input);
backtrack(a,k,input);
if (finished) return; /* terminate early */
unmake_move(a,k,input);
}
}
}
What is confusing me is the if-else: If is_a_solution is True, then the else code won't execute. But let's say we want to find all possible solutions. Then, even if you've found a solution a[0...k], wouldn't you want to continue extending the solution to see if more solutions exists down the solution tree? Essentially, why isn't the code like this:
...
if (is_a_solution(a,k,input))
process_solution(a,k,input);
k = k+1;
...
```
atakes, the solutions appear only in the leaves. I was going to say that this is not the most general form of backtrack, but who knows whatmake_moveandunmake_movecould be doing. Potentially they manage (explicitly or implicitly) another tree of partial solutions in which the solutions are not necessarily at leaves. Let me then say only that it is another way of writing a backtracking algorithm. $\endgroup$ – plop Aug 16 '20 at 1:33