algorithm - 导出 nqueens 问题的时间复杂度

Question

谁能证明/推导出我的 nqueens 解决方案方法的时间复杂度？
我正在遍历网格上的每一个位置，如果可以在那里放置一个女王，那么，我正在计算解决方案，首先放置女王然后取消放置女王，否则我继续前进。

代码：

bool notinrow(int row,int col,vector<string> tra)
  {
      for(int i=0;i<tra.size();i++)
      {
          if(tra[row][i]=='Q' & i!=col)
              return false;
      }
      return true;
  }  
bool notincol(int row,int col,vector<string> tra)
  {
   for(int j=0;j<tra.size();j++)   
   {
       if(tra[j][col]=='Q' & j!=row)
         return false;
   }
    return true;  
  }
 bool notindiag1(int r,int c, vector<string> tra)
  {
      int i=r-1;
      int j=c-1;
      while(i>=0 & j>=0)
      {
          if(tra[i][j]=='Q')
              return false;
          i--;j--;
      }   
      return true;
  } 
bool notindiag2(int r, int c,vector<string> tra)
  {  int i=r-1;
      int j=c+1;
      while(i>=0 & j<totqueens)
      {
          if(tra[i][j]=='Q')
              return false;
          i--;j++;
      }   
      return true;
  }    
  void nqueens(int number,vector<string> tra,int currqueens)
    {
      if(currqueens==totqueens)
      { 
       bhej.push_back(tra);
       return ;
      } 
      if(number==totiter)
          return;  
      int x=number/totqueens;
      int y=number%totqueens;
      if(ispossible(x,y,tra))
      {       
        tra[x][y]='Q';
        nqueens(number+1,tra,currqueens+1);
        tra[x][y]='.';
        nqueens(number+1,tra,currqueens) ; 
      }
      else
        nqueens(number+1,tra,currqueens); 
   }```

标签： algorithmtime-complexityn-queens