c - C 中的数独求解器。程序在某些情况下停止，我不知道为什么

Question

我正在为一个解决数独难题的类编写一个 C 程序。我们应该实现三种方法，首先，它在每个只有一个可能选择的方格中放置正确的数字，重复直到不再找到任何数字。接下来，它使用蛮力，在每个方格中放置尽可能小的数字。我有这两种方法。最后一种方法是带有回溯的暴力破解，它是暴力破解功能的一部分。它的工作方式与常规蛮力相同，只不过它到达一个无法在其中放置数字的方 block ，然后移动到前一个方 block 并放置下一个最大的数字。一旦实现，这应该可以解决所有给定的数独难题，但这就是我遇到麻烦的地方。

我已经实现了所有三种方法，并且我们得到了不同的数独谜题示例，有些可以仅使用第一个“单选”方法来解决，有些可以仅使用“单选”和“没有回溯的暴力破解”以及其他使用“单一选择”和“回溯暴力破解”的方法。我的程序既适用于“单选”谜题，也适用于“单选”和“无回溯的暴力破解”谜题。但是，它不适用于“单选”和“回溯暴力”谜题。

但我不明白的奇怪部分是，对于回溯难题，程序甚至在调用暴力函数之前就停止工作了。

这是我的主要功能:

#include <stdio.h>
#include "sudokusolver.h"
int main()
{
   int puzzle[9][9], i, j, count, attempts=0, backTracks=0;
   readSudoku(puzzle);
   printf("a\n");
   do
   {
      count=0;
      for(i=0;i<9;i++)
      {
         for(j=0;j<9;j++)
         {
            if(singleCandidate(puzzle, i, j)==1)
               count++;
         }
      }
   }while(count!=0);
   bruteForce(puzzle, &attempts, &backTracks);
   printSudoku(puzzle);
   return 0;
}

我使用“printf("a\n")”来显示程序停止工作的位置。

这是一个有效的输出示例。这是一个使用“单选”方法和“无回溯暴力”的数独谜题示例。请注意，零代表拼图中的空格。:

Enter line 1: 010042000
Enter line 2: 008053010
Enter line 3: 900071560
Enter line 4: 400700600
Enter line 5: 067205130
Enter line 6: 002004005
Enter line 7: 080430001
Enter line 8: 030120700
Enter line 9: 000580090
a
315|642|987
678|953|412
924|871|563
-----------
453|718|629
867|295|134
192|364|875
-----------
786|439|251
539|126|748
241|587|396

这是一个不起作用的输出示例。这是一个必须使用“单一选择”和“回溯强力”来解决的示例难题:

Enter line 1: 300910750
Enter line 2: 100570009
Enter line 3: 009000000
Enter line 4: 020740090
Enter line 5: 900000003
Enter line 6: 010069020
Enter line 7: 000000300
Enter line 8: 700085006
Enter line 9: 098034002
^C

程序继续运行，就好像它处于无限循环中，^C 是我退出程序。正如你所看到的，程序甚至从未到达它在数独谜题中读取的正下方的 printf("a") ，甚至在它调用“回溯蛮力”函数之前，这很奇怪，因为它只是谜题需要强力回溯，但不起作用。

这是 readSudoku 函数，它似乎被卡住了:

void readSudoku(int puzzle[][9])
{
   int i, j;
   for(i=0;i<9;i++)
   {
      printf("Enter line %d: ", i+1);
      for(j=0;j<9;j++)
      {
         scanf("%1d", &puzzle[i][j]);
      }
   }
}

这是实现回溯的暴力破解函数

void bruteForce(int puzzle[][9], int *attempt, int *backtracks)
{
   int stable[9][9], i, j, k, found=0, temp=0;
   for(i=0;i<9;i++)
   {
      for(j=0;j<9;j++)
      {
         if(puzzle[i][j]==0)
            stable[i][j]=0;
         else
            stable[i][j]=1;
      }
   }
   for(i=0;i<9;i++)
   {
      for(j=0;j<9;j++)
      {
         for(k=0;k<9;k++)
         {
            if(checkValid(puzzle, i, j, k+1)==1)
            {
               puzzle[i][j]=k+1;
               break;
            }
            if(k==8)
               break;
         }

         while(puzzle[i][j]==0)
         {
            found=0;
            temp=j-1;
            for(j=temp;j>=0;j--)
            {
               if(stable[i][j]==0)
               {
                  found=1;
                  break;
               }
            }
            temp=i-1;
            if(found==0)
            {
               for(i=temp;i>=0;i--)
               {
                  for(j=8;j>=0;j--)
                  {
                     if(stable[i][j]==0)
                     {
                        found=1;
                        break;
                     }
                  }
               if(found==1)
                  break;
               }
            }
            found=0;
            temp=puzzle[i][j]+1;
            for(k=temp;k<9;k++)
            {
               if(checkValid(puzzle, i, j, k+1)==1)
               {
                  found=1;
                  puzzle[i][j]=k+1;
                  break;
               }
            }
            if(found==0)
               puzzle[i][j]=0;
         }
      }
   }
}

这是一个非常奇怪的问题，对我来说完全没有意义，感谢任何帮助。

Answer 1

我猜问题可能出在 singleCandidate() 中。我看不到它的来源，但你应该验证它在不改变谜题时不会返回 1，因为这会导致无限循环。

还要检查当您收到无效输入时(即当数独无解时)它的行为方式。