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

Question

Here is the code for NQueen that i created. There are few operations like calling the nqueen function, then from nqueen->calling backtrack, which does the recursion and put value "1" on dynamically allocated array "arr". The problem is, since i've initialized variable "n" in main and passed into nqueen & from nqueen to backtrack and sometimes to print the final created complete nqueen array , "n" is passed to print function. The value of "n" is decreasing in every recursive call , well in some of them, but there is no decrementing operation i've provided.

this is the main , calling nqueen func passing "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;
}

here is the nqueen function called by passing "arr" and "n" and calling backtrack() passing the same "arr" and "n" . but now the value of n is getting changed somehow.

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

this is the backtrack() code after nqueen calls code

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;
}

this is the overall code with some functions like print and check array for queens for diagonal and sideways for that "i" and "j" position

#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;
}

if someone could please check and provide me the solution to it. Thanks!

Answer 1

As Jarod42 wrote:

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.

You are watching "n" which is another (=local) "n". Because of your recursive call.

But I also get a Segfault if I execute this. You call check function with a value "4" for i. That will access arr with invalid offset in line:

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

Valid values only go from 0 up to 3 for array of size 4. EDIT: of course the i is 4 because before the recursive call is made, there is i++ without any check if this gets higher as it is allowed to. I don't really get what the purpose of this code is, so maybe it's enough to check if i and j are valid and stop if not.