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);        }    }}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)?
Why does backtracking work the way it does?
algorithms;recursion;backtracking
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).