8 クイーン問題を解く C# アルゴリズムの簡単な分析

8つのクイーンの問題の説明:

8 クイーン問題は古くからある有名な問題であり、バックトラッキングアルゴリズムの典型的な例です。この問題は、19 世紀の有名な数学者ガウスによって 1850 年に提唱されました。8X8 のチェス盤に 8 つのクイーンを配置するときに、クイーン同士が攻撃し合わないように、つまり、同じ行、列、または対角線上に 2 つのクイーンがないようにするには、何通りの方法があるでしょうか。

C# アルゴリズムによるソリューション:

公共 クラスクイーン
 { 
  パブリッククイーン()
  { 
    //  
    // TODO: ここにコンストラクタロジックを追加します 
    //  
  } 
  プライベート 静的  bool [] 列フラグ = new  ブール[8]{真, 
  true 、 true 、 true 、 true 、 true 、 true 、 true }; //列占有マーク true は使用可能であることを意味する 
  プライベート 静的  bool [] 左フラグ =新規 ブール[15]{真,真,真, 
  true 、 true 、 true 、 true 、 true 、 true 、 true 、 true 、 true 、 true 、 true 、 true }; // 左列の対角占有マーク 
  プライベート 静的  bool [] 右フラグ = new  ブール[15]{真,真, 
  true 、 true 、 true 、 true 、 true 、 true 、 true 、 true 、 true 、 true 、 true 、 true 、 true }; //右斜め占有マーク 
  プライベート 静的  int [,] 位置 =新しい 整数[,]{{0,0,0,0,0,0,0,0,0},
   {0,0,0,0,0,0,0,0,0},
   {0,0,0,0,0,0,0,0,0},
   {0,0,0,0,0,0,0,0,0},
   {0,0,0,0,0,0,0,0,0},
   {0,0,0,0,0,0,0,0,0},
   {0,0,0,0,0,0,0,0,0},
   {0,0,0,0,0,0,0,0,0}
             }; //クイーンの位置座標 
  プライベート 静的 整数合計=0; 
    
  公共 静的  void TryStep( int i) //iの範囲は1から8  
  { 
    ( int j=1;j<=8;j++)の場合
   { 
     if (columflag[j-1]&&leftflag[i+j-2]&&rightflag[i-j+7]) //現在の位置を 
    {
     列フラグ[j-1] = false ;
     左フラグ[i+j-2] = false ;
     rightflag[i-j+7]= false ; //占有 
 
     position[i-1,j-1]=1; //クイーンの位置を追加 
     もし(i<8)
     {
      TryStep(i+1); //次の行を入力する 
     } 
     それ以外 
     {
      sum++; //ソリューション統計 
      Console.WriteLine( "" );
      Console.WriteLine( "{0} 番目のソリューション:" ,sum);
      Console.WriteLine( "" ); 
 
       for ( int m=0;m<8;m++) // 解答を印刷 
      { 
        ( int n=0;n<8;n++)の場合
       {
        Console.Write( "{0} " 、位置[m,n]);
       }
       Console.Write( "\n" ); 
        
      } 
 
     } 
 
     columflag[j-1] = true ; // 配置できない場合は、席をキャンセルしてクイーンを削除します 
     左フラグ[i+j-2] = true ;
     右フラグ[i-j+7] = true ;
     位置[i-1,j-1]=0; 
       
    } 
 
   }
  }
 }