This is a simple code example of backtraking. This traverses the problem space in depth-first order. I memorized it as a solution template.
const int MAXC = 4;
int finished = 0;
void bt(int a[], int k, int n) {
int candidates[MAXC], numCand, i;
if (solved(a, k, n)) {
answer(a, k, n);
return;
}
numCand = getCandidates(a, k, n, candidates);
for (i = 0; i < numCand; i++) {
a[k] = candidates[i];
bt(a, k + 1, n);
if (finished) return;
}
}
Top comments (0)