0

独自の通常の 9x9 数独パズルを作成しようとしています。

問題を2つの部分に分けました -

  1. 完全に埋められた数独を作成し、
  2. グリッドから不要な数字を削除する

今、私は最初の部分で立ち往生しています。

これは私が簡単に使用するアルゴリズムです:

a) まず、数字 (たとえば 1) を選択し、ランダムなセル位置を生成し、次の場合はそこに配置します。

  • セルがまだ占有されていない
  • 行に番号がまだない場合、および
  • 列に番号がまだない場合、および
  • 3x3 ボックスに番号がまだない場合

b) 次に、行、列、またはボックスの 1 つの場所だけが空である状況を確認し、それを埋めます。

c）ボックスには存在しないが、同じ行と同じ列のボックスに存在する数字がある場合（ここでは3x3ボックスについて話している）、数字の場所が固定されていることを確認し、それを埋めます.

d) すべての数字がグリッドに 9 回表示されるまで、上記の手順を繰り返します。

私が直面している問題は、多くの場合、次のような中間的な状況になっていることです。

 0  1  0 | 0  0  3 | 0[4/2]0 
 0 [2] 0 | 0 [4] 1 | 3  0  0 
 3  0 [4]|[2] 0  0 | 0  0  1 
---------+---------+---------
 2  0  3 | 0  5  4 | 0  1  0 
 0  0  1 | 3  0  2 |[4] 0  0 
 0  4  0 | 0  1  0 |[2] 3  0 
---------+---------+---------
 1  0  2 | 0  3  0 | 0  0 [4] 
 4  3  0 | 1  0  0 | 0  0 [2] 
 5  0  0 | 4  2  0 | 1  0  3

[4/2]と書かれているところが見えますか？[] とマークされたボックスのため、これは 2 と 4 の場所です。

この状況に陥らないようにするにはどうすればよいですか (この状況はデッドロックであるため、これ以上先に進むことができません)

4

3 に答える 3

4

数独パズルを生成する別の方法があります: 既知の適切なグリッドから始めます (どのグリッドでも構いません)。次に、不変条件を破壊しない操作を適用してランダムに「シャッフル」します。有効な操作は次のとおりです。

  • ブロック内の行の交換
  • ブロック内の列の交換
  • ブロックの行全体を入れ替える (例: 最初の 3 行、中間の 3 行、最後の 3 行)
  • ブロックの列全体を交換する
  • ある数値のすべてのインスタンスを別の数値と交換する
  • ボードの反映
  • ボードの回転

これらの操作を使用すると、非常に広範囲の可能なボードを生成できます。ただし、操作を適用する方法には注意が必要です。単純なシャッフルと同様に、一部のボードが他のボードよりも可能性が高くなるアルゴリズムを作成するのは簡単です。ここでは、クヌース シャッフルに似たテクニックが役立ちます。

編集:これらの操作だけでは、可能なすべてのグリッドを作成するには不十分であることがコメントで指摘されています。

于 2009-10-15T09:13:01.737 に答える
1

あなたはいつもそのような状況に陥ります。それを解決するには、再帰的なバックトラッキング検索が必要です。

基本的に、特定の数字がセルに対して本当に有効かどうかを判断する唯一の方法は、検索を続けて何が起こるかを確認することです。

バックトラッキング検索は通常、再帰呼び出しを使用して行われます。各呼び出しは、1 つのセルに対して (おそらく) まだ有効なオプションを反復処理し、次のセルのすべてのオプションを再帰的に評価します。続行できない場合、バックトラックとは、現在の呼び出しから戻ることを意味します。もちろん、最初にそのセルでテストした数字を消去します。

有効な解決策を見つけたら、それを保存してバックトラックして続行する (つまり、代替案を見つける) か、すべての再帰呼び出しを中断して終了します。再帰的なバックトラッキング検索での成功は、成功のために例外をスローすることが IMO の良い考えである特殊なケースです。特定の呼び出しが成功することは例外的であり、コードはより明確になります。

ランダム ボードを生成する場合は、(特定のセルに対する) 特定の再帰呼び出しでオプションをランダムな順序で繰り返します。

同じ基本アルゴリズムが部分的に完成したボードにも適用されます (つまり、既存の数独を解くため) - 既に数字があるセルを評価する場合、そのセルの唯一のオプションなので、次のセルに再帰します。

これは、私がかつて書いたソルバーからのバックトラッキング検索です。多くのことが抽象化されていますが、うまくいけば、原理がより明確になります...

size_t Board::Rec_Search (size_t p_Pos)
{
  size_t l_Count = 0;

  if (p_Pos == 81)  //  Found a solution
  {
    l_Count++;

    std::cout << "------------------------" << std::endl;
    Draw ();
    std::cout << "------------------------" << std::endl;
  }
  else
  {
    if (m_Board [p_Pos] == 0)  //  Need to search here
    {
      size_t l_Valid_Set = Valid_Set (p_Pos);

      if (l_Valid_Set != 0)  //  Can only continue if there are possible digits
      {
        size_t  l_Bit = 1;  //  Scan position for valid set

        for (size_t i = 1; i <= 9; i++)
        {
          if (l_Valid_Set & l_Bit)
          {
            Set_Digit  (p_Pos, i);
            l_Count += Rec_Search (p_Pos + 1);
          }

          l_Bit <<= 1;
        }

        Clr_Digit (p_Pos);  //  Ensure cleared properly for backtracking
      }
    }
    else  //  Already filled in - skip
    {
      l_Count += Rec_Search (p_Pos + 1);
    }
  }

  return l_Count;
}
于 2009-10-15T09:49:40.437 に答える
0

セルが 2 と 4 の場合、他の 2 と 4 のいくつかを間違って配置する必要があるという矛盾した状態に達した場合。ロールバックして、いくつかの異なるソリューションを試す必要があります。

アルゴリズムに問題があるようですね？ここにいくつかの良いものがあります。

于 2009-10-15T08:29:31.920 に答える