The [NQueen problem](http://en.wikipedia.org/wiki/Eight_queens_puzzle) is a famous example of [backtracking](http://en.wikipedia.org/wiki/Backtracking). After reading from the [source](http://www.geeksforgeeks.org/archives/13387), 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](http://ideone.com/tjo69) as: 

```
1 5 8 6 3 7 2 4 

```

However, when i comment the statement which backtracks, I am getting the same [output](http://ideone.com/Rkfl5) 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?
['https://Stackoverflow.com/questions/12070601', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1347366/']
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.
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);

}

```