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