4

この関数がどのように機能するかを理解しようとしています。数独パズルを生成するためのいくつかのアルゴリズムを研究し、これを見つけました。

関数をテストしたところ、有効な 9x9 ラテン方陣 (数独) グリッドが生成されました。私の問題は、関数がどのように機能するか理解できないことです。構造体が ints、p および b によって形成されることは知っています。 p はテーブル内のセルの番号を保持しますが、その後は理由がわかりませんより多くの配列（タブ1とタブ2）を作成し、ラテン正方形をチェックする方法 =/ などを要約すると、完全に失われました。

この関数の背後にある一般的な概念である行ごとの説明を求めているわけではありません。私を大いに助けてくれるでしょう！

もう一度ありがとう<3

int sudoku(struct sudoku tabla[9][9],int x,int y)
{
int tab[9] = {1,1,1,1,1,1,1,1,1};
        int i,j;
  for(i=0;i<y;++i)
  {
        tab[tabla[x][i].p-1]=0; 

  for(i=0;i<x;++i)
  { 
        tab[tabla[i][y].p-1]=0;
  }
  for(i=(3*(x/3));i<(3*(x/3)+3);++i)
  { 
        for(j=(3*(y/3));j<y;++j)
        {
         tab[tabla[i][j].p-1]=0; 
        }
  }
    int n=0;
   for(i=0;i<9;++i)
   {
    n=n+tab[i];
   }

    int *tab2; 
    tab2=(int*)malloc(sizeof(int)*n);

    j=0; 
    for(i=0;i<9;++i)
    { if(tab[i]==1)
      {
       tab2[j]=i+1;
            j++;
      }
    }
    int ny, nx;
    if(x==8)
    {
        ny=y+1; 
        nx=0;   
    }
    else
    {
        ny=y; 
        nx=x+1;
    }

    while(n>0)
    {
        int los=rand()%n;
        tabla[x][y].p=tab2[los];

        tab2[los]=tab2[n-1]; 

        n--;

        if(x==8 && y==8)
        {
            return 1;
        }

        if (sudoku(tabla,nx,ny)==1)
        {
           return 1;
        } 

    }
    return 0;
}

EDIT 素晴らしい、私は構造を理解しました。lijie の回答に感謝します。私がまだ理解していないのは、ランダムな順序で値を試す部分です)。また、乱数を配置した後、グリッドが再度有効かどうかを確認する必要がありますか? –</p>

4

3 に答える 3

3

(x, y)基本的に、関数の呼び出しはtable のat と "after" の位置を埋め、tabla関数は "before" の位置が埋められていると仮定し(x, y)、値の正当な "fill in" が可能かどうかを返します。

ボードは、x を増やしてから y を増やすことで線形化されます。

関数の最初の部分は で有効な値を見つけ(x, y)、2 番目の部分はランダムな順序で値を試し、再帰呼び出しによってボードの残りの部分を埋めようとします。

その目的で再利用できるtab2ため、実際には意味がありません。また、関数はメモリをリークします (決してd ではありませんが、これらを除けば機能します)。tabfree

これはあなたにとって意味がありますか？

編集

正当な番号をチェックする部分で唯一トリッキーな領域は、3 番目のループ (3x3 ボックスをチェックする) です。の条件jはj < y、これらの値がj == y2 番目のループによって既にチェックされているためです。

EDIT2

私はつまらないものを選びますが、法的な値を数えnて埋める部分tab2は本当に

int n = 0;
for (i = 0; i < 9; ++i) if (tab[i]) tab[n++] = i+1;

したがって、 の必要性を省略しますtab2(後のコードでは、の代わりにtabandを使用できます)。したがって、メモリリークは解消されます。ntab2

編集

ランダム性は有効な値にのみ適用されることに注意してください (値自体ではなく、値を試す順序がランダム化されます)。

コードは、標準的な徹底的な検索パターンに従います。考えられる各候補値を試し、検索が成功した場合はすぐに戻り、すべての候補値が失敗した場合は失敗してバックトラックします。

于 2010-11-28T16:49:32.983 に答える
1

原則の簡単な説明 - 投稿した例は無視します。うまくいけば、アイデアがあれば、自分で例に結び付けることができます。

基本的なアプローチは、少なくとも 80 年代の終わり頃まで見られたように、多くの「人工知能」の基礎となったものです。多くのパズルに対する最も一般的な解決策は、基本的にすべての可能な解決策を試すことです。

したがって、最初に左上隅に 1 があるすべての可能な解決策を試し、次に左上隅に 2 があるすべての可能な解決策を試します。再帰して、2 番目の位置、3 番目の位置などのオプションを試します。これは、徹底的な検索、または「ブルート フォース」と呼ばれます。

問題は、ほとんど永遠にかかることですが、多くの無意味な検索をショートカットすることができます.

たとえば、左上隅に 1 を配置すると、再帰します。次の位置に 1 を配置し、もう一度再帰します。しかし、ボードの残りの部分を埋めなくても、2 つのルール (2 つの行に 1 つ、3x3 のブロックに 2 つのルール) に違反していることに気付きます。したがって、「バックトラック」します。つまり、再帰を終了して前のレベルに戻り、その 2 番目の位置に 2 を配置します。

これにより、多くの検索が回避され、物事が実用的になります。各行、列、およびブロックでまだ使用されていない数字を追跡している場合は、さらに最適化することもできます。これらのセットの交差について考えてみてください。

私が説明したことは、実際にはソリューション アルゴリズムです (一部のセルが既に入力されている場合)。ランダムに解決された数独を生成することは同じことですが、数字の位置ごとに、数字をランダムな順序で試す必要があります。これにより、パズルを解決できることを確認しながら空白のままにするセルを決定し、(はるかに難しい) 難易度設定でパズルを設計するという問題も残ります。しかし、ある意味では、これらの問題に対する基本的なアプローチはすでにここにあります。たとえば、ソリューション アルゴリズムを実行し、ソリューションが得られるかどうか (およびその数) を調べることで、特定の左空白のセットが有効かどうかをテストできます。空白のままの有効なセル セットの検索を設計できます。

難易度のことは、人間の難易度に依存するので難しいです。うーん、「難しい」をどこかにもう一度入れてもいいですか...

1 つのアプローチ - 再帰的検索に優先して典型的な人間の経験則を使用し、必要な再帰の最も深いレベルとして難易度を判断する、より洗練された検索アルゴリズムを設計します。一部の経験則は、他のものよりも高度であると判断される場合もあるため、それらを使用すると難易度が高くなります。明らかに難易度は主観的なものであるため、採点をどの程度正確に行うべきかについて、唯一の正解はありません。

これにより、特定のパズルの難易度がわかります。難易度のレベルに合わせてパズルを直接設計するのは難しいでしょう - しかし、空白のままにするセルのさまざまな選択を試すときは、複数のオプションを試し、すべての難易度スコアを追跡し、最後に自分に最も近いものを選択することができます目標難易度。

于 2010-11-28T17:36:27.277 に答える
1

数独を自分で解こうとすると、解を見つけるのに固有の再帰があることがわかります。したがって、ボード全体が解決されるまで自分自身を呼び出す関数があります。

コードに関しては、大幅に簡素化できますが、自分で作成しようとすると最適です。

編集：

これはJavaからのものです。おそらく、あなたがやろうとしていることと似ているでしょう。

于 2010-11-28T16:40:25.227 に答える