5．4 　８王妃問題
番号 以下をクリックすると，該当箇所にジャンプします （１） ８王妃問題とは （２） 解を求める方法 --- ［プログラム例］ （１）８王妃問題とは　 ８王妃問題（8 Queen problem)とは，８×８のチェス盤上に， 8個の王妃が互いに取りあうことのないように配置する問題です。 チェスの王妃は， 縦・横・斜めライン上のコマをとることができます。 いわば，将棋の飛車と角の働きを併せ持つコマです。 　　　　　　　　 たとえば，次のように配置すると， 互いに取りあうことはありません。 　　　　　　　　　　　　　　　　 （２）解を求める方法 8個の王妃を配置する方法は， 　　６４×６３×６２×６１×６０×５９×５８×５７ 　　＝１７８，４６２，９８７，６３７，７６０ とおりあります。 この組合せをすべて列挙して， それぞれが条件を満足するかどうかを 調べるのは，大変です。現実的でもありません。 そこで，まず，次のように配置を行うものとします。 　　�@）各列に，王妃は1個だけ配置する。 　　�A）各行に，王妃は1個だけ配置する。 これによって，以下の組合せ数に減ります。 　　　　８×７×６×５×４×２×１＝４０，３２０（＝８！） これだけでもずいぶん少なくなってはいますが， 以下のような配置も含まれています。 そこで，以下のような斜め方向を限定するための フラグの配列を用意することで，限定操作を行います。 　　　　　［斜め方向限定用のフラグＡ］ 　　　　　 　　　　　［斜め方向限定用のフラグＢ］ 　　　　　 番号 以下をクリックすると，該当箇所にジャンプします （１） ８王妃問題とは （２） 解を求める方法 --- ［プログラム例］ ［プログラム例］ 　　ラベルの位置で，チェス盤を表現します。 private int 解番号=0; private bool[] 行配置済み=new bool[8]; 　　　　　　　　　　 //　各行に王妃が配置済みかどうかを示す private bool[] 対角配置済みA=new bool[15]; 　　　　　　　　　　 //　対角／に王妃が配置済みかどうかを示す private bool[] 対角配置済みB=new bool[15]; 　　　　　　　　　　//　対角＼に王妃が配置済みかどうかを示す private int[] 列位置= new int[8]; 　　　　　　　　　　// 各列の王妃の位置 private Label[,] LabelDT= new Label[8,8]; private void 表示() { 　　int i,j; 　　for(j=0;j<8;j++) 　　　 { 　　　　　　for(i=0;i<8;i++) LabelDT[j,i].Text=""; 　　　　　　LabelDT[j,列位置[j]].Text="●"; 　　　　} 　 解番号++; 　　MessageBox.Show(解番号.ToString() + "番目の解表示"); } private void 設定(int i)　　// 解の設定 { 　　int j; 　　for (j =0; j<8; j++) 　　{ 　　　　if(!行配置済み[j] && !対角配置済みA[i+j] 　　　　　　　　　　　　　　　&& !対角配置済みB[i-j+7]) 　　　　{ 　　　　　　列位置[i]=j; 　　　　　　if (i==7) 表示(); 　　　　　　else 　　　　　　{　　// 行配置 　　　　　　　　行配置済み[j] =対角配置済みA[i+j] 　　　　　　　　　　　　　　　　　=対角配置済みB[i-j+7]=true; 　　　　　　　　// 再帰的に呼び出す。 　　　　　　　　設定(i+1); 　　　　　　　　// 元に戻す 　　　　　　　　行配置済み[j] =対角配置済みA[i+j] 　　　　　　　　　　　　　　　　　=対角配置済みB[i-j+7]=false; 　　　　　　} 　　　　　} 　　　} } private void 初期化() { 　　int i, j, X, ID; bool Flag; string Name; 　　X=-8; 　　for(i=0;i<8;i++)　　　 // ラベルの2次元配列化 　　{ 　　　　X +=8; 　　　　for(j=0;j<8;j++) 　　　　{ 　　　　　　ID=X+j+1; 　　　　　　Name="label" + ID.ToString(); 　　　　　　Flag=true; 　　　　　　foreach(Control myControl in this.Controls) 　　　　　　　　　if(myControl.Name==Name) 　　　　　　　　　{ 　　　　　　　　　　　Flag=false; 　　　　　　　　　　　LabelDT[i,j]=(Label) myControl; 　　　　　　　　　　　break; 　　　　　　　　　} 　　　　　　if(Flag) MessageBox.Show("初期化に失敗しました"); 　　　　　} 　　} 　　// 列位置，フラグ類の初期化 　　for(i=0;i<8;i++) 列位置[i]=0; 　　for(i=0;i<8;i++) 行配置済み[i]=false; 　　for(i=0;i<15;i++) 対角配置済みA[i]= 対角配置済みB[i]=false; } private void button1_Click(object sender, System.EventArgs e) { 　　解番号=0; 　　設定(0); 　　MessageBox.Show(解番号.ToString() 　　　　　　　　　　　　　　+ "個の解が求められました．"); } private void Form1_Load(object sender, System.EventArgs e) { 　　初期化(); } i 番号 以下をクリックすると，該当箇所にジャンプします （１） ８王妃問題とは （２） 解を求める方法 --- ［プログラム例］ 1. 基本的なアルゴリズム 2. 基本的なデータ構造 3. 操作を伴うデータ構造 4. 探索 5. 再帰的アルゴリズム 6. ソート 7. 集合 8. 文字列処理 9. 色々なアルゴリズム 上のタイトルをクリックします