Time complexity of N Queen using backtracking?

Question

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

void printboard(int n);
void fourQueen(int k,int n);
int place(int k,int i);
int x[100];

void NQueen(int k,int n)
{
  int i;
  for(i=1;i<=n;i++)
  {
    if(place(k,i)==1)
    {     x[k]=i;
            if(k==n)
            {
                printf("Solution\n");
                printboard(n);
            }
            else
                NQueen(k+1,n);
    }
  }
}

int place(int k,int i)
{
  int j;
  for(j=1;j<k;j++)
  {
    if((x[j]==i)||abs(x[j]-i)==abs(j-k))
        return 0;
  }
  return 1;
}

void printboard(int n)
{
  int i;
  for(i=1;i<=n;i++)
    printf("%d  ",x[i]);
}

void main()
{
    int n;
    printf("Enter Value of N:");
    scanf("%d",&n);
    NQueen(1,n);
}

I think it has time complexity: O(n^n), As NQueen function is recursively calling, but is there is any tighter bound possible for this program? what about best case, and worst case time complexity. I am also confused about the place() function which is O(k) and calling from NQueen().

Answer 1

There are a lot of optimizations than can improve the time complexity of the algorithm.

There is more information in these links:

1. https://sites.google.com/site/nqueensolver/home/algorithm-results

2. https://sites.google.com/site/nqueensolver/home/algorithms/2backtracking-algorithm

Answer 2

For Your function T(n) = n*T(n-1) + O(n^2) which translates to O(N!) time complexity approximately.