我的变量 "n" 正在自行递减，甚至没有提供递减操作。 C++ - N_Queen_Problem 程序

Question

这是我为 NQueen 创建的代码。很少有像调用 nqueen 函数，然后从 nqueen->calling backtrack 进行递归并将值“1”放在动态分配的数组 "arr" 上的操作。问题是，因为我已经在 main 中初始化变量 "n" 并传递给 nqueen & 从 nqueen 到回溯，有时打印最终创建的完整 nqueen 数组，"n" 被传递给打印函数。 "n" 的值在每个递归调用中都在递减，其中一些递归调用是这样，但是我没有提供递减操作。

这是主要的，调用 nqueen 函数传递 "n"=4->

int main(){
int n=4;
int** arr=new int*[n];
for(int i=0;i<n;i++){
    arr[i]=new int[n];
}
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        arr[i][j]=0;
    }
}
print(arr,n);
int num=nqueen(arr, n);
cout<<num<<endl;

return 0;
}

这里是通过传递 "arr" 和 "n" 并调用 backtrack() 传递相同的 "arr" 和 "n" 调用的 nqueen 函数。但现在 n 的值正在以某种方式改变。

int nqueen(int** arr,int n){
   int count=0;
   for(int i=0;i<n;i++){
     count+=backtrack(arr,i,n);
   }
   return count;
}

这是nqueen调用代码后的backtrack()代码

int backtrack(int** arr,int i,int n){
    if(i==n) return 0;
    int count=0;
    for(int j=0;j<n;j++){
      if(check(arr,i,j,n)==0){
        arr[i][j]=1;
            cout<<"\n"<<i<<" "<<j<<" "<<n<<endl;
            print(arr,n);
        i++;
        count+=backtrack(arr,i,j);
        i--;
        arr[i][j]=0;
       }
     }
    return count;
}

这是包含一些功能的整体代码，例如打印和检查皇后数组的对角线和横向 "i" 和 "j" 位置

#include<iostream>
using namespace std;


int nqueen(int** arr,int n);
void print(int** arr,int n);
int backtrack(int** arr,int i,int n);
int check(int** arr,int i,int j,int n);

int backtrack(int** arr,int i,int n){
if(i==n) return 0;
int count=0;
for(int j=0;j<n;j++){
    if(check(arr,i,j,n)==0){
        arr[i][j]=1;
            cout<<"\n"<<i<<" "<<j<<" "<<n<<endl;
            print(arr,n);
        i++;
        count+=backtrack(arr,i,j);
        i--;
        arr[i][j]=0;
    }
}
return count;
}

int nqueen(int** arr,int n){
int count=0;
for(int i=0;i<n;i++){
    count+=backtrack(arr,i,n);
}
return count;
}

int check(int** arr, int i,int j,int n){
/////check vertical horizontal
for(int k=0;k<n;k++){
    if(arr[i][k]==1) return 1;
    if(arr[k][j]==1) return 1;
}
/////check diagonal
int k=i,l=j;
while(k<n&&l<n){
    if(arr[k][l]==1){
        return 1;
    }
    k++;
    l++;
}

k=i,l=j;
while(k>=0&&l>=0){
    if(arr[k][l]==1){
        return 1;
    }
    k--;
    l--;
}

k=i,l=j;
while(k>=0&&l<n){
    if(arr[k][l]==1){
        return 1;
    }
    k--;
    l++;
}

k=i,l=j;
while(k<n&&l>=0){
    if(arr[k][l]==1){
        return 1;
    }
    k++;
    l--;
}

return 0;
}

void print(int** arr,int n){
cout<<endl;
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        cout<<arr[i][j]<<" "<<i<<j<<" ";
    }
    cout<<endl;
}
}

int main(){
int n=4;
int** arr=new int*[n];
for(int i=0;i<n;i++){
    arr[i]=new int[n];
}
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        arr[i][j]=0;
    }
}
print(arr,n);
int num=nqueen(arr, n);
cout<<num<<endl;

return 0;
}

如果有人可以检查并向我提供解决方案。谢谢！

Answer 1

正如 Jarod42 所写：

You call backtrack(arr,i,j)... So n from int backtrack(int** arr,int i,int n) would be that j, but n from main is unchanged.

您正在观看 "n"，这是另一个（=本地）"n"。因为你的递归调用。

但是如果我执行这个，我也会得到一个段错误。你为 i 调用值为“4”的检查函数。这将访问具有无效偏移量的 arr：

if(arr[i][k]==1) return 1;

对于大小为 4 的数组，有效值只能从 0 到 3。编辑：当然 i 是 4 因为在进行递归调用之前 i++ 没有任何检查它是否变得更高，因为它是允许的。我真的不明白这段代码的目的是什么，所以也许检查 i 和 j 是否有效就足够了，如果无效则停止。

我的变量 "n" 正在自行递减，甚至没有提供递减操作。 C++ - N_Queen_Problem 程序

My variable "n" is decrementing on its own ,without even providing decrement operation. C++ - N_Queen_Problem Program

c++

algorithm

recursion

backtracking

n-queens