N Queens Puzzle - Where is the Backtracking in this solution?

Question

While studying the well known N Queens puzzle, I came across this straightforward and easy to understand implementation in C:

#include<stdio.h>
#include<math.h>

int board[20],count;

int main()
{
 int n,i,j;
 void queen(int row,int n);

 printf(" - N Queens Problem Using Backtracking -");
 printf("\n\nEnter number of Queens:");
 scanf("%d",&n);
 queen(1,n);
 return 0;
}

//function for printing the solution
void print(int n)
{
 int i,j;
 printf("\n\nSolution %d:\n\n",++count);

 for(i=1;i<=n;++i)
  printf("\t%d",i);

 for(i=1;i<=n;++i)
 {
  printf("\n\n%d",i);
  for(j=1;j<=n;++j) //for nxn board
  {
   if(board[i]==j)
    printf("\tQ"); //queen at i,j position
   else
    printf("\t-"); //empty slot
  }
 }
}

/*funtion to check conflicts
If no conflict for desired postion returns 1 otherwise returns 0*/
int place(int row,int column)
{
 int i;
 for(i=1;i<=row-1;++i)
 {
  //checking column and digonal conflicts
  if(board[i]==column)
   return 0;
  else
   if(abs(board[i]-column)==abs(i-row))
    return 0;
 }

 return 1; //no conflicts
}

//function to check for proper positioning of queen
void queen(int row,int n)
{
 int column;
 for(column=1;column<=n;++column)
 {
  if(place(row,column))
  {
   board[row]=column; //no conflicts so place queen
   if(row==n) //dead end
    print(n); //printing the board configuration
   else //try queen with next position
    queen(row+1,n);
  }
 }
}

However, as much as most of it looks correct to me, I cannot see the backtracking in it. What am I missing?

In my opinion, in the queen() function, there should be a check after the for loop to see whether the search exhausted without success for that particular row/queen, and if so, backtrack by simply calling itself with row-1. Is this assumption correct?

Answer 1

let's get deeper look in this code:

void queen(int row,int n)
{
 int column;
 for(column=1;column<=n;++column)
 {
  if(place(row,column))
  {
   board[row]=column; //no conflicts so place queen
   if(row==n) //dead end
    print(n); //printing the board configuration
   else //try queen with next position
    queen(row+1,n);
  }
 }
}

Yes, it's backtracking. Since it'll try every possible solution candidate until the some finish condition. on some row value, for(column=1;column<=n;++column) will ensure to try every possible value of column and check if it feasible with place(row,column), then go deeper to row+1. After finishing this, this algorithm will resume to next column.

In other word, this algorithm will print every possible solution, of n-queen.