0
$\begingroup$

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;
         ...
```
$\endgroup$
  • 1
    $\begingroup$ They assume that in the tree of partial solutions represented by different values that the array a takes, 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 what make_move and unmake_move could 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 at 1:33
  • $\begingroup$ Please have a look at what's (off- and) on-topic with COMPUTERSCIENCE @SE. $\endgroup$ – greybeard Aug 16 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.