C语言回溯式填字游戏算法故障排查求助

一、解决段错误的核心问题 #

• 未初始化的填字数组：main中声明char crossword[MAX_DIMENSION][MAX_DIMENSION];后，数组内存为随机垃圾值。读取黑格坐标时直接赋值#，但后续循环仅将!= '#'的位置设为_——若垃圾值恰好等于#，会导致本该是空白的位置被误判为黑格，引发后续越界或逻辑错误。
  修复：声明数组后先全局初始化所有元素为_，再处理黑格，同时添加坐标合法性检查：

  char crossword[MAX_DIMENSION][MAX_DIMENSION];
  // 先初始化所有位置为空白
  for (i = 0; i < MAX_DIMENSION; i++) {
      memset(crossword[i], '_', MAX_DIMENSION);
  }
  // 再设置黑格，同时检查坐标合法性
  while (fscanf(crossword_file, "%d %d", &width, &height) != EOF) {
      int x = width - 1;
      int y = height - 1;
      if (x >= dimension || y >= dimension || x < 0 || y < 0) {
          printf("Invalid black square coordinate: %d %d\n", width, height);
          continue;
      }
      crossword[x][y] = '#';
  }
  

• 字典数组越界风险：若字典文件中的单词数量超过MAX_WORDS（150000），num_words会溢出数组边界，破坏内存。
  修复：读取单词时添加数量检查：

  while (fgets(buffer, 30, dict_file) != NULL) {
      if (num_words >= MAX_WORDS) {
          printf("Warning: Dictionary exceeds MAX_WORDS, truncating.\n");
          break;
      }
      // 原有处理逻辑...
  }
  

• 单词读取缓冲区溢出：buffer长度为30，若字典中有超过28字符的单词（含换行符），会导致缓冲区溢出。
  修复：增大缓冲区并添加长度限制：

  char buffer[100]; // 增大缓冲区
  while (fgets(buffer, sizeof(buffer), dict_file) != NULL) {
      int word_length = strlen(buffer);
      if (word_length > 29) { // 限制单词长度不超过29（匹配words数组的30长度）
          printf("Skipping long word: %s\n", buffer);
          continue;
      }
      // 原有处理逻辑...
  }
  

二、修复错误解的逻辑问题 #

• 回溯时错误覆盖原有字符：当前代码放置单词后，回溯直接将位置设为_，但这些位置可能已经被之前放置的单词填充了有效字母，导致回溯破坏已有的正确填写。
  修复：放置单词前保存原有字符，回溯时恢复（横向放置示例）：

  if (is_valid) {
      int word_len = strlen(words[word_index]);
      // 保存原有字符
      char original[word_len];
      for (k = 0; k < word_len; k++) {
          original[k] = crossword[i][j + k];
      }
      // 放置单词
      for (k = 0; k < word_len; k++) {
          crossword[i][j + k] = words[word_index][k];
      }
      // 递归调用
      if (solve_crossword(dimension, crossword, words, num_words, word_index + 1)) {
          return 1;
      }
      // 回溯恢复原有字符
      for (k = 0; k < word_len; k++) {
          crossword[i][j + k] = original[k];
      }
  }
  

  纵向放置逻辑同理修改。

• 单词放置时未检查路径上的黑格：当前仅判断起始位置不是#，但单词覆盖的后续位置可能是黑格，导致非法覆盖。
  修复：在检查合法性时，额外判断每个位置是否为黑格：

  int is_valid = 1;
  int word_len = strlen(words[word_index]);
  for (k = 0; k < word_len; k++) {
      if (crossword[i][j + k] == '#' || (crossword[i][j + k] != '_' && crossword[i][j + k] != words[word_index][k])) {
          is_valid = 0;
          break;
      }
  }
  

• 无效的is_valid_word函数：该函数逻辑混乱（全局遍历所有格子检查匹配）且未被调用，直接删除即可，后续优化时再重新设计针对性的合法性检查函数。

• 单词放置范围错误：横向放置时，j的循环条件应为j <= dimension - word_len（而非j < dimension - word_len），否则最后一个合法起始位置会被遗漏。

三、调试技巧 #

• 使用GDB调试段错误：编译时添加-g参数，运行gdb ./your_program，触发段错误后用bt命令查看调用栈，定位出错的行。
• 打印中间状态：在solve_crossword函数中，每次放置单词后打印当前填字板状态，观察错误发生的时机和位置。
• 缩小测试用例：先用小字典（比如10个单词）和小尺寸填字板（比如5x5）测试，快速定位逻辑错误，再逐步放大规模。

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