[Solved]: Why does backtracking work the way it does?

Problem Detail: 

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

Asked By : andreas.vitikan

Answered By : Pål GD

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9590