Backtracking Implementation

backtrack.c

int finished = 0;                       /* found all solutions yet? */

template <class T>
backtrack(int a[], int k, T * input)
{
        T 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];
                        backtrack(a,k,input);
			if (finished) return;	/* terminate early */
                }
        }
}