5．5 騎士巡歴問題
番号 以下をクリックすると，該当箇所にジャンプします （１） 騎士巡歴問題とは （２） 解を求める方法 --- ［プログラム例］ （１）騎士巡歴問題とは　 騎士巡歴（Knight‘s Tour)問題とは， Ｎ×Ｎのマス目上のすべてを チェスのナイトが訪れるような 順序を求める問題です。 チェスのナイトは， 進行方向に対して+2,直交方向に+1だけジャンプします。 　　　　　　　　　 いわば，将棋の桂馬と似た働きをします。 正確にいうと，もし，５×５のマス目の中央にナイトがいたとすると， 以下の赤丸印の８方向にジャンプできます。 　　　　　　　 （２）解を求める方法 最初（１，１）の位置にいるものとします。 ナイトがジャンプできる方向に，順次動いていくものとします。 　　　　　 ジャンプできる方向は，8通りありますから， 以下のような表を作成しておきます。 　�@）行先表[0].X= 2; 行先表[0].Y= 1; 　�A）行先表[1].X= 1; 行先表[1].Y= 2; 　�B）行先表[2].X=-1; 行先表[2].Y= 2; 　�C）行先表[3].X=-2; 行先表[3].Y= 1; 　�D）行先表[4].X=-2; 行先表[4].Y=-1; 　�E）行先表[5].X=-1; 行先表[5].Y=-2; 　�F）行先表[6].X= 1; 行先表[6].Y=-2; 　�G）行先表[7].X= 2; 行先表[7].Y=-1; これらの行き先に，すでにコマがあれば，失敗とみなし， 最大到着数（２５コマ）に達すれば成功とします。 番号 以下をクリックすると，該当箇所にジャンプします （１） 騎士巡歴問題とは （２） 解を求める方法 --- ［プログラム例］ ［プログラム例］ 　　ラベルの位置で，チェス盤を表現します。 　　　 [実行例］ 　　　　　　　　 public const int NSIZE = 5; public Label[,] LabelDT = new Label[NSIZE+1,NSIZE+1]; public int[,] 盤面 = new int[NSIZE+1,NSIZE+1]; public int 到達最大数 = NSIZE*NSIZE; public int 解番号 = 0; public int 到達数 = 0; public struct 行先 { 　　public int X; 　　public int Y; } public 行先[] 行先表 = new 行先[8]; private void 初期設定() { 　　int i,j, ID; string labelName; 　　int X=-5; for(i=1;i<6;i++)　　// 盤面用ラベルの2次元配列化 　　{ 　　　　X=X+5; 　　　　for(j=1;j<6;j++) 　　　　{ 　　　　　　ID = X +j; 　　　　　　labelName="label" + ID.ToString(); 　　　　　　foreach( Control myControl in Controls) 　　　　 　　　　if(myControl.Name==labelName) 　　　　　　　　 { 　　　　　　 　 　　LabelDT[i,j]=(Label) myControl; 　　　　　　　　　　break; 　　　　　　　　　} 　　　　 } 　　} 　　行先表[0].X= 2; 行先表[0].Y= 1; // 行き先表の設定 　　行先表[1].X= 1; 行先表[1].Y= 2; 　　行先表[2].X=-1; 行先表[2].Y= 2; 　　行先表[3].X=-2; 行先表[3].Y= 1; 　　行先表[4].X=-2; 行先表[4].Y=-1; 　　行先表[5].X=-1; 行先表[5].Y=-2; 　　行先表[6].X= 1; 行先表[6].Y=-2; 　　行先表[7].X= 2; 行先表[7].Y=-1; } private void 表示() { 　　int i,j; 　　for(i=1;i<6;i++) 　　　　for(j=1;j<6;j++) 　　　　　　LabelDT[i,j].Text=盤面[i,j].ToString(); 　　解番号++; 　　MessageBox.Show(解番号.ToString() 　　　　　　　　　　　　　　 +"番目の解が見つかりました"); } private void Try(int X,int Y) { 　　int i; 　　if(X<1 || X>NSIZE || Y<1 || Y>NSIZE) return; 　　if(盤面[X,Y]>0) return; 　　到達数++; 　　盤面[X,Y] = 到達数; 　　if(到達数>=到達最大数) 表示(); 　　else 　　　　 for(i=0;i<8;i++) Try(X+行先表[i].X,Y+行先表[i].Y); 　　盤面[X,Y]=0; 　　到達数--; } private void Form1_Load(object sender, System.EventArgs e) { 　　初期設定(); } private void button1_Click(object sender, System.EventArgs e) { 　　int i,j; 　　for(i=1; i<=NSIZE;i++)　for(j=1;j<=NSIZE;j++)　盤面[i,j]=0; 　　解番号=0; 到達数=0; 　　Try(1,1); 　　lblMessage.Text="解の数=" +解番号.ToString()+"通り" 　　MessageBox.Show(解番号.ToString() 　　　　　　　　　　　　　　 + "個の解が見つかりました"); } i 番号 以下をクリックすると，該当箇所にジャンプします （１） 騎士巡歴問題とは （２） 解を求める方法 --- ［プログラム例］ 1. 基本的なアルゴリズム 2. 基本的なデータ構造 3. 操作を伴うデータ構造 4. 探索 5. 再帰的アルゴリズム 6. ソート 7. 集合 8. 文字列処理 9. 色々なアルゴリズム 上のタイトルをクリックします