C语言实现八皇后问题时出现Segmentation Fault求助

问题描述 #

尝试解决经典八皇后问题时，程序执行到棋盘状态00377455后触发Segmentation Fault（段错误）。使用数组存储棋盘状态避免整数溢出，检查各函数逻辑未发现问题，编译环境为gcc，调试工具为VS Code。

段错误原因分析 #

核心问题出在getNextBoard函数的递归逻辑中：

• 当遍历到最后一个棋盘状态77777777时，调用getNextBoard(chessBoard,7)会触发连续进位，直到处理第0位；
• 第0位原值为7，加1模8后变为0，此时函数会递归调用getNextBoard(chessBoard, -1)；
• 访问chessBoard[-1]属于数组越界访问，触发非法内存操作，最终导致段错误。

此外，countPossibilities函数未处理getNextBoard返回NULL的情况，即使函数返回空指针，仍会继续递归访问空指针指向的内存，进一步加剧错误。

修复后的代码 #

#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){
  // 处理n小于0的边界情况，直接返回NULL
  if(n < 0) return NULL;
  
  int prev_val = chessBoard[n];
  chessBoard[n] = (prev_val + 1) % 8;
  
  if(chessBoard[n] == 0){
    // 第0位进位后回到0，说明所有状态遍历完成
    if(n == 0) return NULL;
    // 否则继续向前递归进位
    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 + (isFit(chessBoard) ? 1 : 0);
  }
  
  int *nextBoard = getNextBoard(chessBoard, 7);
  // 检查是否遍历完所有状态
  if(nextBoard == NULL){
    return n + (isFit(chessBoard) ? 1 : 0);
  }
  
  if(isFit(chessBoard)){
    return countPossibilities(nextBoard, n+1);
  } else {
    return countPossibilities(nextBoard, 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("Total solutions: %d\n", ft_eight_queens_puzzle());
  return 0;
}

代码改进意见 #

• 优化遍历逻辑：当前代码暴力枚举所有8^8=16777216种棋盘状态，效率极低。建议改用回溯法，逐行放置皇后，一旦发现当前行无法合法放置，直接回溯到上一行，避免无效枚举。
• 减少重复计算：isFit函数每次都检查所有行的冲突，可在放置皇后时实时记录列、正对角线、反对角线的占用情况，O(1)时间判断是否冲突。
• 避免递归溢出：当前countPossibilities采用递归遍历，极端情况下可能触发栈溢出。可改用循环实现状态遍历，更稳定且性能更好。
• 代码可读性优化：
  • 给变量起更有意义的名字（如tab改为chessBoard）；
  • 增加函数注释，说明每个函数的功能、参数和返回值；
  • 适当添加空行分隔代码块，提升可读性。

内容的提问来源于stack exchange，提问作者imranbout