segmentation fault while trying to solve the eight queens problem in C

Question

Here I am trying to solve the infamous eight queens problem. When I finally thought I got it, a segmentation fault hits me out of nowhere. The code:

#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("     %d\n",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 gives a segmentation fault. Any help would be 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. I tried to check if any of my fuctions aren't working, but all seems good.

I use gcc to compile and visual studio code to debug.

~edit:

I would also appreciate any comments or criticisms on my code that would help to improve it.

Answer 1

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("     %d\n", 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.

Your getNextBoard() is also a tail recursion, and can also be written as a loop. No recursion is needed for your brute-force solution. You are simply stepping through all possible boards with one queen per row.

As for suggestions, a little pruning goes a long way. Do your isFit() check for the preceding rows as you add each piece to the board. Don't proceed with that piece in that position if it doesn't fit. Then you will find that you only need to look at less than 2000 intermediate boards, as opposed to 16,777,216 completed boards. This is when you will find recursion useful.

Answer 2

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