授業中に説明したKnight's Tour（騎士の巡回）の解を求めるプログラムを用いて、チェス盤の１辺Nが5と6の場合について、経路の数を求めよ。スタート地点は(0,0)とする。また、そのときの時間計算量（制御ループの一番内側のif文の評価回数で表すものとする）を、桁あふれがないように注意しつつ求めよ。
以下のものを提出してください。
|
【注意】 | |
| 誰かに教えてもらった場合： | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合： | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合： | 教えてもらった・教えてあげたの例に準拠して提出してください。 |
| プログラム先頭の様子 |
|
Closed Knight's Tour（騎士の周遊）とは、Knight's Tourに加えて、経路の最後のマスからスタート地点に１手で戻れる経路を求める問題である。チェス盤の１辺Nが5と6の場合について、この条件を満たす経路の数を求めよ。また、実行時間も示せ。
下記に示すチェス盤では、移動できる部分をoで、移動できない部分をxで示している。このようなチェス盤に対する Closed Knight's Tour の解の総数を求める問題に対して、時間計算量を見積もった上で、プログラムを実行し、解の総数と時間計算量（評価回数）を求めよ。また、得られた結果と時間計算量の見積とのずれの理由を考察せよ。
課題に利用するマップ
| マップG | マップJ | マップM | マップN | マップZ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|