C语言 使用回溯的 N Queen 的时间复杂度？

Time complexity of N Queen using backtracking?

提问by tanmoy

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

我认为它有时间复杂度：O(n^n)，因为 NQueen 函数是递归调用的，但是这个程序是否有更严格的限制？最好的情况和最坏情况的时间复杂度呢？我也对 O(k) 和从 NQueen() 调用的 place() 函数感到困惑。

回答by Juan Ramirez

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

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

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

回答by Vikram Bhat

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

对于您的功能T(n) = n*T(n-1) + O(n^2)，O(N!)平均而言转化为时间复杂度。

回答by Shyam Bhimani

TIME COMPLEXITY OF N-QUEEN PROBLEM IS

N-皇后问题的时间复杂度是

> O(N!)

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

解释：如果我们将所有这些加起来并将运行时间定义为 T(N)。然后 T(N) = O(N2) + N*T(N-1)。如果您使用此循环绘制递归树，则最后一项将类似于 n3+ n!O(1)。根据 Big O 的定义，这可以减少到 O(n!) 运行时间。

回答by aman_41907

The complexity is n^n and here is the explanation

复杂度是 n^n，这里是解释

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.

这里 n 代表皇后的数量，并且在每次函数调用时都保持不变。K 是行号，函数将被调用次数直到 k 达到 n。如果 n=8，我们有 n 行和 n 个皇后。

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

T(n)=n(n+t(max of k - 1))=n^max of k=n^n 因为 k 的最大值是 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.

注意：该函数有两个参数。在循环中，n 不减少，对于每个函数调用它保持不变。但是对于函数被调用的次数，它正在减少，以便递归可以终止。

回答by Akshay

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

O(n^n) 绝对是使用回溯解决 n-queens 的上限。我假设你是通过分配一个皇后列来解决这个问题的。但是，请考虑这一点 - 当您在第一列中指定皇后的位置时，您有 n 个选项，之后，您只有 n-1 个选项，因为您不能将皇后与第一个皇后放在同一行，然后n-2等等。因此，最坏情况的复杂度仍然是 O(n!) 的上限。

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

希望这能回答您的问题，即使我晚了将近 4 年！

回答by Mohit Gupta

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.

在这种情况O(N!)下，时间复杂度将是最坏的情况，假设我们正在寻找是否存在任何解决方案。这里有一个简单的解释。

Let us take an example where N=4.

让我们举一个例子，其中 N=4。

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

假设我们要填充二维矩阵。X代表一个空缺职位，而1代表一个已采取的职位。

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 optionsas one row has already been taken off. Similarly, for the third row, we have 2 optionsand for the final row, we are left with just 1 option.

对于第一行，由于没有填充整个矩阵，我们有4 options. 对于第二排，我们有3 options一行已经被取下。同样，对于第三行，我们有，2 options而对于最后一行，我们只剩下1 option.

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

总选项 = 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.

现在，如果我们的皇后是车，情况就是这样，但是因为我们在皇后的情况下有更多的限制。复杂性应低于O(N!)实际操作次数。