首页 文章

C中的Sudoku Solver程序在某些情况下会停止，我不知道为什么

提问于
浏览 次
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;
         }
      }
   }
}

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

c sudoku backtracking solver

2 回答

  • 0

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

    还要检查当您获得无效输入时它的行为（即当数独没有解决方案时） .

    回复于
  • 2

    在你的_1586629中，你有

    /* 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 的起始值设置为大于先前猜测的值 . But you try to set the cell to 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) 返回 1 为某些 k ，那么你开始尝试再次解决这个难题，导致进入相同的循环 .

    不可否认，如果终端设置为正常缓冲模式， printf("a\n"); 应打印出 a ，但我认为打印缓冲区更有可能不会被刷新 readSudoku 神奇地检测到需要回溯并且拒绝对它们进行处理的谜题 .

    回复于

相关问题