1

ランダム グリッド、ラテン方陣、数独を生成するプログラムに取り組んでいます。私はラテン方陣に取り組んでおり、連続ループにいることを除いて、ほとんどすべてが機能しています。それらを分割すると、正常に動作します。おそらく私が間違っている小さな何かがあり、それを見つけることができません。何が悪いのか分かりますか？

編集：ラテン方陣が何であるかを知らない人のために（誰かが知らない場合）、通常は行にも列にも繰り返しがない9x9グリッドです.

更新: if(notSame) ステートメントの直前に、notSame が true に等しいという問題が見つかりました。常に true に等しいため、行のチェックが終了しませんでした。実行すると、連続ループではなくなりましたが、代わりに行には繰り返しがありませんが、列にはまだ繰り返しがあります。

更新 #2: 列のコーディングの多くをやり直しました。私の教授は私にいくつかのことを変更するように頼みましたが、それでも私は継続的なループに陥っています.

int row = 0, col = 0, count = 0;
bool notSame = true;
// setting up rows and columns
for (row = 0; row < grid.GetLength(0); row++)
{
   for (col = 0; col < grid.GetLength(1); col++)
   {

       grid[row, col] = rnd.Next(1, 10);

       //for loop to check rows for repeats
       for (int c = 0; c < col; c++)
       {
           // if there is repeat go back a column and set bool = false
           if (grid[row, col] == grid[row, c])
           {
               col--;
               count++;
               notSame = false;
               break;
            }

            //notSame = true;
        }

     // if bool = true loop to check columns for repeats
     if (notSame)
     {

         for (int r = 0; r < row; r++)
         {
         // if repeat then go back row
            if (grid[row, col] == grid[r, col])
            {
                notSame = false;
                count++;
                break;
             }

          }
          if (notSame == false && count <= 50)
          {
               row--;
               //break;
          }
          else if (notSame == false && count > 50)
          {
               count = 0;
               col = 0;
               row = 0;
               break;
          }
      }
   }
}

グリッドと呼ばれる 2D 配列を使用しています。

4

4 に答える 4

2

あなたのコーディングエラーがどこにあるかわかりません。しかし、あなたのアルゴリズムはあまり効率的ではありません。

ラテン方陣と数独はどちらも、実際には「グラフの色付け」問題の特殊なケースです。つまり、任意に「接続」された一連の「ノード」が与えられた場合、接続された 2 つのノードが同じ色にならないように各ノードに色を付ける方法を見つけます。

この問題は、一般にすぐに解決するのは非常に困難ですが、数独やラテン方陣の特定のケースでは、C# で簡単に解決できます。81 個のノードを持つ「グラフ」を作成すると、各ノードは行と列の他のノードに「接続」されます。「色」は1から9までの数字です。

5 部構成の記事シリーズでは、数独を解くことができる効率的なグラフの色付けアルゴリズムを作成する方法について説明します。代わりに数独を生成するようにアルゴリズムを適応させることは難しくありません。

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

于 2012-03-28T18:25:27.893 に答える
2

私の問題は、行のチェックでの余分なカウントでした。カウントは常に 50 を超えるため、無限ループが発生します。明確にするために：

grid[row, col] = rnd.Next(1, 10);

   //for loop to check rows for repeats
   for (int c = 0; c < col; c++)
   {
       // if there is repeat go back a column and set bool = false
       if (grid[row, col] == grid[row, c])
       {
           col--;
           count++;
           notSame = false;
           break;
        }

        //notSame = true;
    }

count++ はインクリメントされ、時々 > = 50 になり、次のコードで開始されます。

 else if (notSame == false && count > 50)
      {
           count = 0;
           col = 0;
           row = 0;
           break;
      }

これにより、すべてが 0 に戻り、再起動します。そのため、無限ループを引き起こしました。助けてくれてありがとう！

于 2012-04-29T20:49:51.330 に答える
1

ラテン方陣を生成する最も簡単な方法は、既知のラテン方陣から始めることだと思います。言う：

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

これは、行の循環順列によって任意のサイズに対して簡単に生成でき、グリッド内の各値 (1,2,3,4) をランダムに生成された別の値に割り当てるだけです。たとえば、数字 1、2、3、4 のリストを単純にシャッフルして、たとえば 2、4、3、1 を取得できます。正方形の 1 をシャッフル リストの最初のエントリに、2 を 2 番目のエントリに、というように置き換えるだけで、次のようになります。

2 4 3 1
4 3 1 2
3 1 2 4 
1 2 4 3

必要に応じて、行（および/または列）の順序をシャッフルすることもできますが、それでも有効なはずです。

編集: 実際、これについて考えると、最初の正方形から始めて、列と行をシャッフルするのがおそらく最も簡単です。置換部分を行う必要はありません。

于 2012-03-28T18:28:36.330 に答える
0

反復している変数を明示的にデクリメントすることはできません。それはおそらくあなたの問題です。これは、バックトラッキングを使用して回避するのに適した場所のようです:)

編集：どこから始めればよいかわからない多くの問題が見られました。このアルゴリズムでは、必要なものが提供されることはありません。まず、入力を開始するとデッドロックの問題が発生する可能性があり、特定の行/列に数値を追加する方法はありません。行5に12345があり、次に列6にあると想像してください。番号678 9 ..ええと、行5、列6に番号を追加することはできません;）そこに問題がありますか？それ以外に、コードにはいくつかの問題があります。反復中に反復変数を変更することは大きな問題であり、回避する必要があります。

一度notSame=false; その後、それはあなたの実行の残りの間そのように残ります。

列は垂直になり、行は水平になるので、この（1,2）は行1の列2です。最初のフェーズで行をチェックし、2番目のフェーズで列をチェックします。

// if bool = true loop to check columns for repeats
     if (notSame)
     {

         for (int r = 0; r < row; r++)
         {
             // if repeat then genereate new random and go back row
             if (grid[row, col] == grid[r , col])
             {
                 grid[row, col] = rnd.Next(1, 10);

それ自体に問題があります。そこで番号を変更した場合は、以前と同じようにチェックされているはずです。

先生にここに来てこれを読むように言ってください;）..他にどのようにあなたを助けるかわかりません、このアルゴリズムは完全に間違っており、完全なリファクタリングが必要です（そして、はい、反復を使用してそれを行うことができますが、 whileとflagsを使用する必要があります）。

于 2012-03-28T18:07:01.753 に答える