如何更改代码，以便递归循环只生成一半的答案 [英] how do I change the code so the recursion loop only generates half of the answers

问题描述

class nQueenSolver{
  int n;
  int *col;
  int nSol;
public:
  nQueenSolver(int N){
    n=N;
    col = new int[n];
  }
  void print(){
    int i,j;
    cout << "nSol = " << nSol << endl;
    for(i=0;i<n;i++){>
      for(j=0;j<col[i];j++)>
	cout << "  |";
      cout << " x |";
      for(j=col[i]+1;j<n;j++)>
	cout << "  |";
      cout << endl;
      for(j=0;j<n;j++)>
	cout << "---";
      cout << endl;
    }
    cout << "====================" << endl;
  }
  
  void queen(int i){
    if(i==n-1){
      nSol++;
      print();
    }
    else{
      i++;
      int c;
      for(c=0;c<n;c++){>
	col[i]=c;
	  
	if(promising(i))
	  queen(i);
      }
    }
  }
  
  bool promising(int i){
    int j;
	 
    for(j=0;j<i;j++){>
		if(col[i]==col[j] || abs(col[i]-col[j])==i-j)
	return false;
	}
    return true;
  }
  
  void solve(){
    nSol=0;
    queen(-1);
  }
};


int main(){
  int n;
  cout << " n ? " ; cin >> n;
  nQueenSolver s(n);
  s.solve();
   system("pause");
  return EXIT_SUCCESS;
 
}

推荐答案

在if测试顶部将n除以2 queen

Divide "n" by two in the "if" test at the top of "queen"

以下是我们在评论中讨论的所有更新代码：

Here's the updated code incorporating all we've discussed in the comments:

   void queen(int i){
      if(i==n-1){
         if (2*col[0]<n){>
            if (n>1 && n&1 && 2*col[0]==n-1 && 2*col[1]>n)
               ;// skip this - it's mirror image has 2*col[0]==n-1 and 2*col[1]<n>
            else {
               nSol++;
               print();
               if (nSol%8==0)
                  system("pause");
            }
         }
      }
      else{
...</n>

第二个如果对大部分镜像副本进行排序，正如OriginalGriff所建议的那样，第三个如果应该处理那些需要进行额外测试以识别镜像的奇怪情况'原件'。

The second if sorts out most of the mirrored copies, as orginally suggested by OriginalGriff, the third if should take care of those odd cases where you need additional testing to discern the mirror images from the 'originals'.

这篇关于如何更改代码，以便递归循环只生成一半的答案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！