#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().
✔️ Solution (Backtracking) This is a common backtracking problem. We can see than the number of ways to place a N queens on a NxN board can get very large since we have N^2 choices at first, then N^2 -1 , N^2 -2 and so on... leading to overall time complexity of O(N^2N) .
The time complexity of Backtracking For example, if the function calls itself two times, then its time complexity is O(2 ^ N), and if it calls three times, then O(3 ^ N) and so on. Hence the time complexity of backtracking can be defined as O(K ^ N), where 'K' is the number of times the function calls itself.
The worst-case “brute force” solution for the N-queens puzzle has an O(N^N) time complexity. This means it will look through every position on an NxN board, N times, for N queens.
A simple bruteforce solution would be to generate all possible chess boards with 8 queens. Accordingly, there would be N^2 positions to place the first queen, N^2 – 1 position to place the second queen and so on. The total time complexity, in this case, would be O(N^(2N)), which is too high.
There are a lot of optimizations than can improve the time complexity of the algorithm.
There is more information in these links:
https://sites.google.com/site/nqueensolver/home/algorithm-results
https://sites.google.com/site/nqueensolver/home/algorithms/2backtracking-algorithm
For Your function T(n) = n*T(n-1) + O(n^2)
which translates to O(N!)
time complexity approximately.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With