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 &lt; 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 &lt;= n; i++)
    {
        cout &lt;&lt; sol[i];
    }
    cout &lt;&lt; endl;
    how++;
}

void backtrack (int k)
{
    if (k == n+1) print();
    else
    {
        sol[k] = 0;
        while (sol[k] &lt; n)
        {
            sol[k]++;
            if (valid(k)) backtrack(k+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)?
for example 1 and 2 relative to 3 are placed correctly, but 1 relative to 2 is placed incorrectly?


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).