# Why does backtracking work the way it does?

I just recently started learning in a CS context (as opposed to a programming context) about simple recursive functions, along with the combinatorial applications, and techniques such as Backtracking and Divide et Impera.

The example problem that I chose for my questions is the n queens problem (given n queens and a n*n chessboard, how do you position the queens such that they can't attack each other?). I understood that the basic idea is to generate all possible placements (by generating a cartesian product) and then simply discarding them as they come along if they are invalid (through the validation function).

Here is my sample implementation:

    int valid (int k)
{
for (int i = 1; i < k; i++)
{
if (sol[i] == sol[k]) return 0;
if (abs(sol[i] - sol[k]) == abs(i - k)) return 0;
}
return 1;
}

void print ()
{
for (int i = 1; i <= n; i++)
{
cout << sol[i];
}
cout << endl;
how++;
}

void backtrack (int k)
{
if (k == n+1) print();
else
{
sol[k] = 0;
while (sol[k] < n)
{
sol[k]++;
if (valid(k)) backtrack(k+1);
}
}
}

1. Why is it that in the validation function, the checking of the solution is done progressively by checking 1 with k, 2 with k and so on. I think that the solution can be correct in pairs of (i, k) but wrong overall (for example 1 and 2 relative to 3 are placed correctly, but 1 relative to 2 is placed incorrectly)?
• Please boil down your implementation to a pseudo code on the right abstraction level (cf here). You will find this to be an excellent exercise. (Are you missing some lines in the beginning?) – Raphael Feb 8 '13 at 8:26
• Your question about the correctness of the validation function has been answered. I merely want to point out that there is no backtracking going on in your code, despite the function names. Backtracking means that if you can find no correct position for a queen in the kth row, you move back to the (k-1)th row, and find a new position for the queen. – Paresh Feb 8 '13 at 14:00

You have already tested that 1 and 2 are placed correctly, otherwise you wouldn't call backtrack(3).
Recall that sol[i] = j means that the queen in column $i$ is put at row $j$. By calling backtrack(k+1) you have already verified that every queen in $1 \dots k$ are placed correctly (non-colliding).