Backtracking

Introduction to Backtracking : http://en.wikipedia.org/wiki/Backtracking

Implementation [1]:

	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 */
	}
	}
	}

view raw backtrack.c hosted with ❤ by GitHub

Simple Exercise : Use the above template to count the number of permutations of 1, 2, 3... n (n > 5) in which 4 and 5 are not neighbours.

[1] - http://www.cs.sunysb.edu/~skiena/392/programs/