0

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

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

虽然我不明白的奇怪部分是，对于回溯谜题，程序在蛮力函数被调用之前就停止了工作。

这是我的主要功能：

#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;
         }
      }
   }
}

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

4

2 回答 2

2

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

还要检查当你得到一个无效输入时它的行为（即当数独没有解决方案时）。

于 2012-05-24T06:25:41.477 回答
0

在你的bruteForce，你有

/* No legal guess found, so backtrack */
while(puzzle[i][j]==0)
{
    /* Find previous guessed position */
    /* the last guess was as puzzle[i][j] */
    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;
}

因此，您将 的起始值设置为k比之前的猜测大一。但是您尝试将单元格设置为k+1，因此您从不尝试将其设置为old_guess + 1。

因此，如果你猜到了correct_value - 1，你永远不会尝试correct_value。对于需要回溯的谜题，极有可能在某个时候发生这种情况。

所以，既然found == 0，你设置puzzle[i][j] = 0并继续回溯，寻找下一个猜测的位置。

但如果你已经处于第一个猜测的位置，

found=0;
temp=j-1;
for(j=temp;j>=0;j--)
{
    if(stable[i][j]==0)
    {
        found=1;
        break;
    }
}
// Here, j == -1
 temp=i-1;
 if(found==0)
 {
     // if i == 0
     for(i=temp;i>=0;i--)
     {
     // i is set to -1 and the loop ends right now, with i == -1 and j == -1
     // if i was > 0, j is decremented from 8 to -1 for all i down to 0 in the inner loop
         for(j=8;j>=0;j--)
         {
             if(stable[i][j]==0)
             {
                 found=1;
                 break;
             }
         }
         if(found==1)
             break;
         // i is finally set to -1, with j still -1
     }
 }
 found=0;
 temp=puzzle[i][j]+1;

然后您正在访问puzzle[-1][-1]，调用未定义的行为。

如果您很不幸，该无效的内存访问不会导致崩溃（似乎是这种情况），可能会checkValid(-1,-1,k+1)返回1some k，那么您开始尝试再次解决难题，导致进入相同的循环。

诚然，如果终端设置为正常缓冲模式，printf("a\n");应该打印出来a，但我认为打印缓冲区没有被刷新的可能性大于readSudoku神奇地检测到需要回溯并拒绝处理它们的谜题。

于 2012-05-24T19:34:27.087 回答