Question 203443 in Visual Studio Code Question posted in
View the official documentation.

Visual Studio Code – segmentation fault while trying to solve the eight queens problem in C

Here i am trying to solve the infamous eight queens problem, and when i finally thought i got it,a segmentation fault hits me out of nowhere, the code i wrote is:

#include<unistd.h>
#include<stdio.h>
int isLastBoard(int *chessBoard){
  for(int i = 0 ; i < 8 ; ++i){
    if(chessBoard[i] != 7)return 0;
  }
  return 1;
}
int isFit(int *tab){
  for(int i = 1; i < 8 ; ++i){
    for(int j = 0 ; j < i ; ++j){
      if(tab[i] == tab[j] || tab[i] == tab[j] + i -j|| tab[i] == tab[j] - i + j)return 0;
    }
  }
  return 1;
}

int *getNextBoard(int chessBoard[], int n){
  if(n == 0 && chessBoard[n] == 7)return NULL;
  chessBoard[n] = (chessBoard[n] + 1) % 8;
  if(chessBoard[n]==0)return getNextBoard(chessBoard,n-1);
  return chessBoard;
}

int countPossibilities(int *chessBoard,int n){
  for(int i = 0 ; i <8 ; ++i){
    printf("%d",chessBoard[i]);
  }
  printf("     %dn",n);
  if(isLastBoard(chessBoard))return n;
  if(isFit(chessBoard))return countPossibilities(getNextBoard(chessBoard,7),n+1);
  return countPossibilities(getNextBoard(chessBoard,7), n);
}
int ft_eight_queens_puzzle(void){
  int chessBoard[8] = {0,0,0,0,0,0,0,0};
  return countPossibilities(chessBoard, 0);
}
int main(void){
  printf("%d", ft_eight_queens_puzzle());
  return 0;
}

the program executes and counts up to the board set 00377455 and then it gives segmentation fault.
any help would be very appreciated

i have tried to use a table instead of an int so that i don’t surpass the int size limit, and because it’s easier, and tried to check if any of my fuctions isn’t working but all seems good.

also i thought it’s worth mentioning that i use gcc to compile and visual studio code to debug.

~edit:
i would also very appreciate any comments or critics towards my code that would help improvising it

Tags:

2

Answers


  1. Chosen as BEST ANSWER
    0

    for anyone from the future who somehow ends up having to deal with the same problem here's a solution:

    #include<unistd.h>
#include<stdio.h>
int isLastBoard(int *chessBoard){
  for(int i = 0 ; i < 8 ; ++i){
    if(chessBoard[i] != 7)return 0;
  }
  return 1;
}
int isFit(int *tab){
  for(int i = 1; i < 8 ; ++i){
    for(int j = 0 ; j < i ; ++j){
      if(tab[i] == tab[j] || tab[i] == tab[j] + i -j|| tab[i] == tab[j] - i + j)return 0;
    }
  }
  for (int i = 0; i < 8; i++)
  {
    printf("%d",tab[i]+1);
  }
  printf("n");
  
  return 1;
}

int *getNextBoard(int chessBoard[], int n){
  if(n <= 0 && chessBoard[n] == 7)return chessBoard;
  chessBoard[n] = (chessBoard[n] + 1) % 8;
  if(chessBoard[n]==0)return getNextBoard(chessBoard,n-1);
  return chessBoard;
}

int countPossibilitiesIn100(int *chessBoard,int n, int stop){
  if(stop >= 100)return n;
  if(isLastBoard(chessBoard))return n;
  if(isFit(chessBoard))return countPossibilitiesIn100(getNextBoard(chessBoard,7),n+1,stop+1);
  return countPossibilitiesIn100(getNextBoard(chessBoard,7), n, stop + 1);
}
int ft_eight_queens_puzzle(void){
  int chessBoard[8] = {0,0,0,0,0,0,0,0};
  int n = 0;
  while (!isLastBoard(chessBoard))
  {
    n = countPossibilitiesIn100(chessBoard,n,0);
  }
  return n;
}
int main(void){
  printf("%d", ft_eight_queens_puzzle());
  return 0;
}

    all i had to do is make the function countPossibilities count only 100 possibilities at a time, so that i don't overflow the stack with recursive returns, and then make it run until it reaches the final case which is 77777777


  2. 0

    Well, looks like you’ve come to the right place. This is a stack overflow problem.

    Your function countPossibilities() is a tail recursion, and so does not need to call itself at all! It is really just a loop. If you write it that way, then no more stack overflow.

    int countPossibilities(int *chessBoard, int n) {
    for (;;) {
        for (int i = 0; i < 8; ++i)
            printf("%d", chessBoard[i]);
        printf("     %dn", n);
        if (isLastBoard(chessBoard))
            return n;
        if (isFit(chessBoard))
            n++;
        getNextBoard(chessBoard, 7);
    }
}

    You were trying to have that function call itself 16,777,216 times (pointlessly), which will blow even the maximum stack that my linker will let me allocate, which is 512MB.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search