Is NQueen really backtracking?

Question

The NQueen problem is a famous example of backtracking. After reading from the source, I have tried the below code snippet.

int isSafe(int k,int i,int *x)
{
    int j;
    for(j=0;j<k;j++)
    {
              //old queen is placed at jth row of x[j] column
              //new queen to be placed at kth row of ith column
            if(i==x[j] || abs(k-j)==abs(i-x[j]))
                    return 0;
    }
    return 1;
}

int Nqueen(int k, int* sol, int N)
{
    int col;
    if( k == N )
    {
            printSol(sol,N);
            return 1;
    }
    else
    {
            for(col = 1;col <= N; col++)  //determines appropriate column number of the kth queen to be placed
            {
                    if( isSafe(k,col,sol) )
                    {
                            sol[k] = col;
                            if( Nqueen(k+1, sol, N) )
                                    return 1;
                            sol[k] = 0; // backtrack
                    }
            }
            return 0; // solution not possible
    }
}

I am getting the output as:

1 5 8 6 3 7 2 4 

However, when i comment the statement which backtracks, I am getting the same output without any problem.

int Nqueen(int k, int* sol, int N)
{
    int col;
    if( k == N )
    {
            printSol(sol,N);
            return 1;
    }
    else
    {
            for(col = 1;col <= N; col++)  //determines appropriate column number of the kth queen to be placed
            {
                    if( isSafe(k,col,sol) )
                    {
                            sol[k] = col;
                            if( Nqueen(k+1, sol, N) )
                                    return 1;
                            // sol[k] = 0; <-------------- Notice this change
                    }
            }
            return 0;
    }
}

What exactly has made NQueen problem, a backtracking one?

Isn't it a simple recursive approach?

Answer 1

The sol[k] = 0 is not the backtracking part. The backtracking is done in the recursive call: if( Nqueen(k+1, sol, N) ).

The idea of backtracking is an exhaustive search - you are trying to search all possibilities, until one is found. In here, you are trying all possible assignments of queens in the board, and "keep on" if it is still safe. If you find it unsafe, you return from the recursion with a failure, and trying the next option.

I believe the commented out line only makes sure that if no solution is found, the resulting array is [0,...,0], and not some nonesense array.

Answer 2

Backtracking Problems are a programming paradigm in which you try each and every possible combination. Then for every combination you check if the combination so far is correct. Below are few steps for N(or 8) queen problem.

1. Start from Row 0 and place 1st queen at Col 0.
2. Now place 2nd queen at Row 1 and col 0.
3. check if position is safe
4. If not safe place 2nd queen at Row 1, col 1.
5. Not Safe, now place 2nd queen at Row 1, col 2.

proceed like this by placing queen at every possible column for each and checking if it is safe. You can omit the obvious false conditions like you won't place 2 queens in a same row. Below is my code for 8 queen problem, printing all possible solutions.

#include<stdio.h>


int abs(int a){
        return a>0? a : -a;
}

int isSafe(int col[],int row){
        int row2,col2,i,yDiff,xDiff;
                if(row == 0) return 1;


    for(row2=0;row2<row;row2++){
                    if(col[row2] == col[row])
                            return 0;

                    xDiff = col[row2] - col[row];
                    xDiff = abs(xDiff);
                    yDiff = row - row2;
                    if(xDiff == yDiff)
                                    return 0;
            }

    return 1;

}

int Nqueen(int col[],int n, int row){
        int i;
        if(row==n){
                printf("\n");
                for(i=0;i<n;i++)
                        printf("%d ",col[i]+1);

        }else{
                for(i=0;i<n;i++){
                    col[row] = i;
                    if(isSafe(col,row)){
                            queen(col,n,row+1);
                    }

            }
    }

}

int main(){
        int col[8];
        queen(col,8,0);

}

Answer 3

First, you really need to understand the algorithm (this will tell you that commenting that stuff out doesn't matter). This algorithm is recursive, as you have noticed. It is backtracking because you

• set the k-th queen to a position
• explore the possible placements for queens k+1,k+2,...
• then you go back to the k-th queen, place it somewhere else, and repeat

See, in step 3 we "go back" to the k-th queen. This is how I explain myself why it's called backtracking.