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

score 16 · Answer 1 · answered Jan 11 '14 at 06:44

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

There is more information in these links:

Snapshot

Vikram Bhat · Answer 2 · 2020-09-22T15:18:18.830

14

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

edited Sep 22 '20 at 15:18

answered Jan 11 '14 at 07:06

Vikram Bhat

6,106
3
20
19

2

kindly explain how that O(n^2)is coming? – Tanmoy Banerjee Jan 11 '14 at 07:13
@tan in if statement u are checking place() which is O(N) and the for loop is O(N) hence O(N^2). – Vikram Bhat Jan 11 '14 at 07:15
@nhahtdh O(N!) < O(N^N) so how can it be stronger bound and how does it seems O(n^n)? solution of T(n) = n*T(n-1) + O(1) gives O(N!). – Vikram Bhat Jan 11 '14 at 12:41
@VikramBhat: Sorry, I do the unrolling in my head and made a mistake. Comment removed. – nhahtdh Jan 11 '14 at 13:02
You have mentioned Avarage? then waht is the worst case time complexity? Please help – Kanagavelu Sugumar Sep 21 '20 at 06:29
@KanagaveluSugumar you are right it shouldn't be in average , but approximately as I am ignoring O(n^2) part to round it off to O(N!) , though the actual time complexity is greater than O(N!) but difficult to evaluate so approximated to N!. – Vikram Bhat Sep 22 '20 at 15:17

score 8 · Answer 3 · edited Dec 16 '17 at 06:32

8

TIME COMPLEXITY OF N-QUEEN PROBLEM IS

> O(N!)

Explanation: If we add all this up and define the run time as T(N). Then T(N) = O(N2) + N*T(N-1). If you draw a recursion tree using this recurrence, the final term will be something like n3+ n!O(1). By the definition of Big O, this can be reduced to O(n!) running time.

edited Dec 16 '17 at 06:32

Tom Aranda

5,919
11
35
51

answered Dec 16 '17 at 05:20

Shyam Bhimani

361
3
8

1

Please explain why. – Tom Aranda Dec 16 '17 at 05:39
If we add all this up and define the run time as T(N). Then T(N) = O(N2) + N*T(N-1). If you draw a recursion tree using this recurrence, the final term will be something like n3+ n!O(1). By the definition of Big O, this can be reduced to O(n!) running time. – Shyam Bhimani Dec 16 '17 at 05:48

score 7 · Answer 4 · edited May 07 '19 at 19:58

O(n^n) is definitely an upper bound on solving n-queens using backtracking. I'm assuming that you are solving this by assigning a queen column-wise. However, consider this - when you assign a location of the queen in the first column, you have n options, after that, you only have n-1 options as you can't place the queen in the same row as the first queen, then n-2 and so on. Thus, the worst-case complexity is still upper bounded by O(n!).

Hope this answers your question even though I'm almost 4 years late!

score 4 · Answer 5 · answered Jul 09 '19 at 19:47

Let us consider that our queen is a rook, meaning we need not take care of diagonal conflicts.

Time complexity in this case will be O(N!) in the worst case, supposed if we were on a hunt to check if any solution exists or not. Here is a simple explanation.

Let us take an example where N=4.

Supposed we are want to fill the 2-D matrix. X represents a vacant position while 1 represents a taken position.

In the starting, the answer matrix (which we need to fill) looks like,

X X X X
X X X X
X X X X
X X X X

Let us fill this row-wise, meaning will select one location in each row then move forward to the next row.

For the first row, since none is filled in the matrix as a whole, we have 4 options. For the second row, we have 3 options as one row has already been taken off. Similarly, for the third row, we have 2 options and for the final row, we are left with just 1 option.

Total options = 4*3*2*1 = 24 (4!)

Now, this was the case had our queen were a rook but since we have more constraints in case of a queen. Complexity should be less than O(N!) in terms of the actual number of operations.

score 2 · Answer 6 · answered Nov 02 '14 at 10:30

The complexity is n^n and here is the explanation

Here n represent the number of of queens and will remain same for every function call. K is the row number and function will be called times till k reaches the n.There if n=8,we have n rows and n queens.

T(n)=n(n+t(max of k - 1))=n^max of k=n^n as the max of k is n.

Note:The function has two parameters.In loop, n is not decreasing ,For every function call it remains same.But for number of times the function is called it is decreasing so that recursion could terminate.

score 0 · Answer 7 · answered Feb 13 '23 at 16:54

0

The complexity is (n+1)!n^n begin with T(i)=O(niT(i+1)), T(n)=n^3. So, T(1)=nT(2)=2n^2T(3)=...=(n-1)n^(n-1)!T(n)=(n+1)

answered Feb 13 '23 at 16:54

Vũ Quang Nam

1

Time complexity of N Queen using backtracking?

7 Answers7

Linked