2

9x9 の数独グリッドを保持する 2 次元配列を想定すると、私のソルブ関数はどこで壊れますか? 単純なバックトラッキング アプローチを使用してこれを解決しようとしています。ありがとう！

bool solve(int grid[9][9])
{
 int i,j,k;
 bool isSolved = false;

  if(!isSolved(grid))
   isSolved = false;

  if(isSolved)
   return isSolved;

  for(i=0; i<9; i++)
  {
   for(j=0; j<9; j++)
   {
    if(grid[i][j] == 0)
    {
     for(k=1; k<=9; k++)
     {
      if(legalMove(grid,i,j,k))
      {
       grid[i][j] = k;
       isSolved = solve(grid);
       if (isSolved)
        return true;
      }
      grid[i][j] = 0;
     }
     isSolved = false;
    }
   }
  }

return isSolved;
}

問題を変更した後でもisSolved、私の解決策は無限ループに陥っているようです。基本的な手順が欠けているように見えますが、その場所や理由がわかりません。同様の解決策を見てきましたが、まだ問題を特定できません。基本的なソルバーを作成しようとしているだけで、効率を上げる必要はありません。助けてくれてありがとう！

4

3 に答える 3

4

ええ、あなたのベースケースはめちゃくちゃです。再帰関数では、基本ケースは最初に処理する必要があります。あなたが得た

bool isSolved = false;

if(!isSolved(grid))
    isSolved = false;

if(isSolved)
    return isSolved;

isSolved変数をtrueに設定することはできないため、コードに注意してください。

if(isSolved)
    return isSolved;

無関係です。

これを修正しても、有限であっても無限ループのように感じます。これは、アルゴリズムには、solveを呼び出すたびにチェックする可能性のある合計9 * 9 * 9=729のケースがあるためです。この関数をn回入力すると、最大729^nのケースをチェックする必要がある場合があります。配置が違法であると行き止まりになるので、明らかに多くのケースをチェックすることはありませんが、可能な数のアレンジメントの90％が、1つを除くすべての数が合法的に適合する場合になると誰が言いますか？さらに、kが小さい数（k <= 10）であるkのケースを平均してチェックしたとしても、これは爆発します（実行時間k ^ n）。

秘訣は、実際に適切な配置である可能性が高い場所に番号を「試行」することです。おそらく、これを行うために私が考えることができる最も簡単な方法は、制約満足度ソルバー、またはヒューリスティック（A *など）を使用した検索アルゴリズムです。

私は実際に制約満足度ソルバーに基づいて数独ソルバーを作成しましたが、100x100の数独を1秒未満で解決します。

奇跡によって、「ブルートフォース」バックトラッキングアルゴリズムが9x9の場合にうまく機能する場合は、より高い値を試してみてください。実行時の劣化がすぐにわかります。

私はバックトラッキングアルゴリズムをバッシングしていません。実際、私はそれが大好きです。正しく実装されていれば、バックトラッキングは動的計画法と同じくらい効率的であることが何度も示されていますが、あなたの場合は正しく実装されていません。あなたはそれを野蛮に強制している、あなたはあなたのコードを非再帰的にしたほうがよいかもしれない、それは同じことを成し遂げるだろう。

于 2009-10-06T05:13:27.730 に答える
3

関数とブール変数の両方としてisSolvedを参照します。これは合法ではないと思いますし、間違いなく賢明ではありません。

関数には、変数とは異なる名前を付ける必要があります。

于 2009-10-06T04:07:37.283 に答える
2

それが正当な動きであるかどうかに関係なく、「grid[i][j] = 0;」で正方形に「0」を割り当てているようです。ライン。たぶん、「else」と THEN「grid[i][j] = 0;」を入れるつもりだったのかもしれません。?

于 2009-10-06T04:32:26.423 に答える