授業中に説明したKnight's Tour（騎士の巡回）の解を求めるプログラムを用いて、チェス盤の１辺Nが5と6の場合について、経路の数を求めよ。
スタート地点は(0,0)とする。
また、存在する経路の数を、桁あふれがないように注意しつつ求めよ。
また、実行時間を計測せよ。
【2010/05/25a版では時間計算量を求めよとありますが、それは発展課題３Ｘのほうです。必須課題３Ａでは単に実行時間を示すだけで構いません。】
|
【注意】 | |
| 誰かに教えてもらった場合： | 教えてくれた学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | 教えてもらった・教えてあげたの例に準拠して提出してください。 |
授業中に説明したKnight's Tour（騎士の巡回）の解を求めるプログラムにおいて、Knightの移動を示す配列を下記のように変更した場合（移動できる方向を課題３Ａとは逆回りに提示するように変更）、解の数と解を求めるのにかかる時間計算量が課題３Ａと比較してどう変化するかを予想し、その理由を述べよ。その際、課題３Ａの結果を引用してよい。なお、実際に実行して検証する必要はない。
| 元の配列 | 変更後のの配列 |
int move[M][2] = {
{ 2 ,1},
{ 1, 2},
{-1, 2},
{-2, 1},
{-2,-1},
{-1,-2},
{ 1,-2},
{ 2,-1}
};
| int move[M][2] = {
{ 2,-1},
{ 1,-2},
{-1,-2},
{-2,-1},
{-2, 1},
{-1, 2},
{ 1, 2},
{ 2 ,1}
};
|
課題３Ａに際して、経路の数だけでなく、そのときの時間計算量（制御ループの一番内側のif文の評価回数で表すものとする）を、桁あふれがないように注意しつつ求めよ。N=5, N=6の両方で行うこと。
|
【注意】 | |
| 誰かに教えてもらった場合： | 教えてくれた学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | 教えてもらった・教えてあげたの例に準拠して提出してください。 |
Closed Knight's Tour（騎士の周遊）とは、Knight's Tourに加えて、経路の最後のマスからスタート地点に１手で戻れる経路を求める問題である。
チェス盤の１辺Nが5と6の場合について、この条件を満たす経路の数を求めよ。また、実行時間も示せ。
下記に示すチェス盤では、移動できる部分をoで、移動できない部分をxで示している。
このようなチェス盤に対する Closed Knight's Tour の解の総数を求める問題に対して、時間計算量を見積もった上で、
プログラムを実行し、解の総数と時間計算量（評価回数）を求めよ。
また、得られた結果と時間計算量の見積とのずれの理由を考察せよ。
課題に利用するマップ
| マップG | マップJ | マップM | マップN | マップZ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|