0

私は数独パズルを解くクラスのためにcのプログラムに取り組んでいます。実装する方法は3つあります。最初に、選択肢が1つしかない各正方形に正しい数字を配置し、見つからなくなるまで繰り返します。次に、力ずくの力を使用して、各正方形に可能な限り少ない数を配置します。私はこれらの2つの方法を機能させています。最後の方法は、ブルートフォース機能の一部であるバックトラッキングを使用したブルートフォースです。通常のブルートフォースと同じように機能しますが、数字を配置できない正方形に到達すると、前の正方形に移動して次に大きい数字を配置します。これが実装されると、これは与えられたすべての数独パズルを解決するはずですが、これは私が問題を抱えているところです。

私は3つの方法すべてを実装しましたが、数独パズルの例をいくつか示しました。最初の「単一選択」方法のみを使用して解決できるものもあれば、「単一選択」と「ブルートフォースなし」のみを使用して解決できるものもあります。 「バックトラッキング」など、「単一選択」と「バックトラッキングによるブルートフォース」を使用するもの。私のプログラムは、「単一選択」パズルと「単一選択」および「バックトラックなしのブルートフォース」パズルの両方で機能します。ただし、「単一選択」および「バックトラックを伴うブルートフォース」パズルでは機能しません。

私が理解していない奇妙な部分は、バックトラックパズルの場合、ブルートフォース関数が呼び出される前にプログラムが動作を停止することです。

これが私の主な機能です：

#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前の推測よりも 1 大きい値に設定します。しかし、セルを に設定しようとする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)が返され、パズルを再び解こうとし始め、同じループに陥ります。1k

確かに、端末が通常のバッファリング モードに設定されている場合は出力する必要がありますが、バックトラックが必要なパズルを魔法のように検出して処理を拒否するよりも、出力バッファがフラッシュされていない可能性の方が高いと思いprintf("a\n");ます。areadSudoku

于 2012-05-24T19:34:27.087 に答える