1
$\begingroup$

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)?
$\endgroup$
  • 3
    $\begingroup$ 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?) $\endgroup$ – Raphael Feb 8 '13 at 8:26
  • $\begingroup$ 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. $\endgroup$ – Paresh Feb 8 '13 at 14:00
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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