Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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)?
share|improve this question
3  
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.