授業中に説明したKnight's Tour（騎士の巡礼）の解を求めるプログラムを用いて、チェス盤のサイズが
(1) ５×５
(2) ５×６
(3) ６×６
の場合の解の数を求めよ。
いずれもスタート地点は(1,1)とする。( (0,0)ではないことに注意！)
それぞれの実行時間（秒単位でよい）を計測し、実行ＣＰＵと環境と合わせて示すこと。
重要:
2012/06/05の授業で示したプログラムは１行抜けていました。
こちらの改訂板書の緑チョーク枠がそれに相当します。
2012/06/12の授業で補足する予定します。
参考：８方向の選択順は特に指定していないが、実行速度等を周りと比較してみたりするには、統一されているほうが便利であろう。そのため、参考までに選択順を示しておく（この通りである必要は別にない）。
| int move[M][2] = { { 2 ,1},{ 1, 2},{-1, 2},{-2, 1},{-2,-1},{-1,-2},{ 1,-2},{ 2,-1} }; |
参考：unix(linux)で実時間で実行時間を計測するプログラム例(gettimeofday関数を利用)
プログラム内で実行時間を計測したい場合の参考にしてください（他の手段でも構いませんが、秒未満の精度で計測できること）。
| 【状況】 | 【指示】 |
| 誰かに教えてもらった場合 | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。
（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合 | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合 | お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 |
上記のKnight's Tourの代わりに、いま、King's Tourを考える。
チェスのKingは将棋の王将と同じく、８方向どの方向にも１マス進むことができる。
もちろん、King's Tourの解は存在するだろう。そのプログラムを作成する際にはKnight's Tourのものをほとんど再利用できる。
Knight's Tourのプログラム(4A-1)から変更してKing' Tourを実行するプログラムを示せ。
(1) 書き換えた部分プログラムにおいて、書き換えた部分を明示し、コメントによって書き換えの趣旨を説明せよ。
(2) 全解探索で時間計算量を見積もった場合、Knight's TourとKing's Tourで差はあるか、ないか？理由とともに答えよ。
(3) 同じ盤のサイズが与えられたとき、Knight's TourとKing's Tourはどちらが解数が多くなると考えられるか？理由とともに答えよ。
(4) 同じ盤のサイズが与えられたとき、Knight's Tourに比べてKing's Tourの実際の実行時間は短くなるか？長くなるか？自分で考える理由と共に答えよ。
※(1)(2)は必ず答えること。(3)(4)は無回答でもよい。(3)(4)は実際に実験してもよいが、推奨はしない。
Knight tourにおいて、８方向の行動選択肢のうちの１つが欠損する場合を考える(Injured Knight Tour)。
課題４Ａの「参考：」にある８方向選択肢のうち、８つめがない状態がこれに相当する。
この場合、解の数は通常のKnight tourと比較して、どのようになると予見されるか？
また、解の数を得るまでにかかる時間はどのように変化するか？
予想を立てて、実際にプログラムを作成・実行し、予想と実際との差異がどうして発生したのか、自分で解説を試みよ。