第四回課題：データ構造とアルゴリズム（２０１１）

データ構造とアルゴリズム, 授業科目, www.kameda-lab.org 2011/06/15a

課題の提出

提出期限
2010/06/20 (Mon), 18:00 JST 【予定：正確にはmoodleで確認してください】
提出方法
筑波大学e-learningポータル(moodle)から提出
条件
「必修」課題は全て提出してください。
「発展」課題の提出は任意です。
（「発展」課題を出さなくともＡ評価になる可能性はありますが、確実に目指すのなら「発展」課題をするほうがよいでしょう）

課題４

★必修：課題４Ａ★

授業中に説明したKnight's Tour（騎士の巡回）の解を求めるプログラムを用いて、チェス盤のサイズが (1) ５×５ (2) ５×６ (3) ６×６の場合について、経路の数を求めよ。スタート地点は(0,0)とする。
このとき、それぞれの実行時間（秒単位でよい）を計測し、実行ＣＰＵと環境と合わせて示すこと。

参考：unix(linux)で実時間で実行時間を計測するプログラム例(gettimeofday関数を利用)
プログラム内で実行時間を計測したい場合の参考にしてください（使わなくても構いません）。

提出物〔4A-1〕：Ｃソースファイル（コメント必須）
５×６の動作確認ができる状態で提出すること。
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
プログラムで工夫した行があれば、必ず何かしらの説明をコメントの形でプログラム中に書き込むこと。

【状況】	【指示】
誰かに教えてもらった場合：	その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。）
誰かに教えてあげた場合：	その学生（氏名・学籍番号）をプログラム先頭に記すこと。
お互いに相談した場合：	お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。

提出物〔4A-2〕：(1) ５×５ (2) ５×６ (3) ６×６に対して、解の数と実行時間を保存したテキストファイル（３つ分まとめること）。実行環境も記述すること。
提出物〔4A-3〕：(1) ５×５ (2) ５×６ (3) ６×６に対して、最初の解を示す盤面を３つずつ（※もし３つ以上あれば３つまで、それ以下ならあるだけ全て；合計最大で９つ）示すテキストファイル。

★必修：課題４Ｂ★
上記のKnight's Tourの代わりに、いま、King's Tourを考える。チェスのKingは将棋の王将と同じく、８方向どの方向にも１マス進むことができる。もちろん、King's Tourの解は存在するだろう。そのプログラムを作成する際にはKnight's Tourのものをほとんど再利用できる。
(1) Knight's Tourのプログラム(4A-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)は実際に実験してもよいが、推奨はしない。
- 提出物〔4B-1,4B-2,4B-3,4B-4〕：テキスト。(1)-(4)に対応
  moodle上で編集して提出してください。バックアップを各個人で別に持っておくことを薦めます。
◆発展：課題４Ｘ◆
課題４Ａの発展として、騎士の周遊(Knight's Tour Round)の解数を (1) ５×５ (2) ５×６ (3) ６×６ について答えるプログラムを作成し実行結果を示せ。
- 提出物〔4X-1〕：Ｃソースファイル（コメント必須）
  ５×６の動作確認ができる状態で提出すること。
  課題4A-1と兼用した場合、同一プログラムファイルでもよいが、ファイルの先頭部分にそのことを明記し、4A-1,4X-1の両方で提出すること。
  Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
  元のプログラムから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
  教えた・教わった場合には、課題４Ａと同様に明記すること。
- 提出物〔4X-2〕：(1) ５×５ (2) ５×６ (3) ６×６に対して、周遊解の数と実行時間を保存したテキストファイル（３つ分まとめること）。実行環境も記述すること。

◆発展：課題４Ｙ◆

ナンプレ(或いは数独^TM)を解くプログラムを改良して、ある問題が与えられているときに、与えられた数字を１つ抜いた場合に解の数がどれほど増えるかを求め、最も解の数を増やしてしまう数字がどれかを求めるプログラムを作成せよ。下記にサンプルを示すが、提出時には各自適当に収集したもので解答すること。

問題サンプル1 サンプル2
出展 Extreme SudokuoのEvilレベルより Sudokuサイトの上級++より
問題
0 0 5 0 0 2 0 0 8 0 6 0 0 1 0 0 5 0 3 0 0 8 0 0 4 0 0 2 0 0 4 0 0 7 0 0 0 9 0 0 6 0 0 3 0 0 0 4 0 0 9 0 0 6 0 0 3 0 0 1 0 0 5 0 7 0 0 2 0 0 4 0 8 0 0 3 0 0 1 0 0

0 2 0 9 0 0 0 0 6 1 0 0 0 0 0 0 9 0 0 0 8 0 0 7 0 0 0 5 0 0 0 0 0 7 0 0 0 0 7 8 0 0 1 0 0 0 0 9 4 0 0 0 0 2 0 0 0 2 0 0 4 0 0 0 6 0 0 0 0 0 0 3 3 0 0 0 0 5 0 8 0
元の正解
4 1 5 6 3 2 9 7 8 9 6 8 7 1 4 3 5 2 3 2 7 8 9 5 4 6 1 2 8 6 4 5 3 7 1 9 5 9 1 2 6 7 8 3 4 7 3 4 1 8 9 5 2 6 6 4 3 9 7 1 2 8 5 1 7 9 5 2 8 6 4 3 8 5 2 3 4 6 1 9 7 (Time = 0.001956 [sec])

4 2 3 9 1 8 5 7 6 1 7 6 5 2 3 8 9 4 9 5 8 6 4 7 3 2 1 5 1 2 3 9 6 7 4 8 6 4 7 8 5 2 1 3 9 8 3 9 4 7 1 6 5 2 7 8 1 2 3 9 4 6 5 2 6 5 7 8 4 9 1 3 3 9 4 1 6 5 2 8 7 (Time = 0.077065 [sec])

本課題解答例
(出力例)
Empty cells = 54, Locked cells = 27 0: [2][0]=5 : ans = 5 1: [5][0]=2 : ans = 14 2: [8][0]=8 : ans = 1 3: [1][1]=6 : ans = 33 4: [4][1]=1 : ans = 1 5: [7][1]=5 : ans = 3 6: [0][2]=3 : ans = 4 7: [3][2]=8 : ans = 25 8: [6][2]=4 : ans = 7 9: [0][3]=2 : ans = 9 10: [3][3]=4 : ans = 12 11: [6][3]=7 : ans = 4 12: [1][4]=9 : ans = 1 13: [4][4]=6 : ans = 2 14: [7][4]=3 : ans = 4 15: [2][5]=4 : ans = 1 16: [5][5]=9 : ans = 5 17: [8][5]=6 : ans = 3 18: [2][6]=3 : ans = 1 19: [5][6]=1 : ans = 6 20: [8][6]=5 : ans = 2 21: [1][7]=7 : ans = 7 22: [4][7]=2 : ans = 1 23: [7][7]=4 : ans = 1 24: [0][8]=8 : ans = 18 25: [3][8]=3 : ans = 5 26: [6][8]=1 : ans = 1 -- If [1][1]=6 is deleted, 33 answers will be found.

Empty cells = 59, Locked cells = 22 0: [1][0]=2 : ans = 145 1: [3][0]=9 : ans = 25 2: [8][0]=6 : ans = 190 3: [0][1]=1 : ans = 7 4: [7][1]=9 : ans = 12 5: [2][2]=8 : ans = 6 6: [5][2]=7 : ans = 37 7: [0][3]=5 : ans = 153 8: [6][3]=7 : ans = 62 9: [2][4]=7 : ans = 43 10: [3][4]=8 : ans = 5 11: [6][4]=1 : ans = 55 12: [2][5]=9 : ans = 9 13: [3][5]=4 : ans = 111 14: [8][5]=2 : ans = 57 15: [3][6]=2 : ans = 63 16: [6][6]=4 : ans = 41 17: [1][7]=6 : ans = 289 18: [8][7]=3 : ans = 11 19: [0][8]=3 : ans = 37 20: [5][8]=5 : ans = 138 21: [7][8]=8 : ans = 24 -- If [1][7]=6 is deleted, 289 answers will be found.

提出物〔4Y-1〕：Ｃソースファイル（コメント必須）
オリジナルのナンプレ問題に対して実行できる状態で提出すること。
出力は上記例に習う必要はないが、同等の情報を示すこと。
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
プログラムで工夫した部分について、説明をコメントの形でプログラム中に書き込むこと。
教えた・教わった場合には、課題４Ａと同様に明記すること。
提出物〔4Y-2〕：実行出力結果を保存したテキストファイル。

kameda[at]iit.tsukuba.ac.jp

問題	サンプル1	サンプル2
出展	Extreme SudokuoのEvilレベルより	Sudokuサイトの上級++より
問題	0 0 5 0 0 2 0 0 8 0 6 0 0 1 0 0 5 0 3 0 0 8 0 0 4 0 0 2 0 0 4 0 0 7 0 0 0 9 0 0 6 0 0 3 0 0 0 4 0 0 9 0 0 6 0 0 3 0 0 1 0 0 5 0 7 0 0 2 0 0 4 0 8 0 0 3 0 0 1 0 0	0 2 0 9 0 0 0 0 6 1 0 0 0 0 0 0 9 0 0 0 8 0 0 7 0 0 0 5 0 0 0 0 0 7 0 0 0 0 7 8 0 0 1 0 0 0 0 9 4 0 0 0 0 2 0 0 0 2 0 0 4 0 0 0 6 0 0 0 0 0 0 3 3 0 0 0 0 5 0 8 0
元の正解	4 1 5 6 3 2 9 7 8 9 6 8 7 1 4 3 5 2 3 2 7 8 9 5 4 6 1 2 8 6 4 5 3 7 1 9 5 9 1 2 6 7 8 3 4 7 3 4 1 8 9 5 2 6 6 4 3 9 7 1 2 8 5 1 7 9 5 2 8 6 4 3 8 5 2 3 4 6 1 9 7 (Time = 0.001956 [sec])	4 2 3 9 1 8 5 7 6 1 7 6 5 2 3 8 9 4 9 5 8 6 4 7 3 2 1 5 1 2 3 9 6 7 4 8 6 4 7 8 5 2 1 3 9 8 3 9 4 7 1 6 5 2 7 8 1 2 3 9 4 6 5 2 6 5 7 8 4 9 1 3 3 9 4 1 6 5 2 8 7 (Time = 0.077065 [sec])
本課題解答例 (出力例)	Empty cells = 54, Locked cells = 27 0: [2][0]=5 : ans = 5 1: [5][0]=2 : ans = 14 2: [8][0]=8 : ans = 1 3: [1][1]=6 : ans = 33 4: [4][1]=1 : ans = 1 5: [7][1]=5 : ans = 3 6: [0][2]=3 : ans = 4 7: [3][2]=8 : ans = 25 8: [6][2]=4 : ans = 7 9: [0][3]=2 : ans = 9 10: [3][3]=4 : ans = 12 11: [6][3]=7 : ans = 4 12: [1][4]=9 : ans = 1 13: [4][4]=6 : ans = 2 14: [7][4]=3 : ans = 4 15: [2][5]=4 : ans = 1 16: [5][5]=9 : ans = 5 17: [8][5]=6 : ans = 3 18: [2][6]=3 : ans = 1 19: [5][6]=1 : ans = 6 20: [8][6]=5 : ans = 2 21: [1][7]=7 : ans = 7 22: [4][7]=2 : ans = 1 23: [7][7]=4 : ans = 1 24: [0][8]=8 : ans = 18 25: [3][8]=3 : ans = 5 26: [6][8]=1 : ans = 1 -- If [1][1]=6 is deleted, 33 answers will be found.	Empty cells = 59, Locked cells = 22 0: [1][0]=2 : ans = 145 1: [3][0]=9 : ans = 25 2: [8][0]=6 : ans = 190 3: [0][1]=1 : ans = 7 4: [7][1]=9 : ans = 12 5: [2][2]=8 : ans = 6 6: [5][2]=7 : ans = 37 7: [0][3]=5 : ans = 153 8: [6][3]=7 : ans = 62 9: [2][4]=7 : ans = 43 10: [3][4]=8 : ans = 5 11: [6][4]=1 : ans = 55 12: [2][5]=9 : ans = 9 13: [3][5]=4 : ans = 111 14: [8][5]=2 : ans = 57 15: [3][6]=2 : ans = 63 16: [6][6]=4 : ans = 41 17: [1][7]=6 : ans = 289 18: [8][7]=3 : ans = 11 19: [0][8]=3 : ans = 37 20: [5][8]=5 : ans = 138 21: [7][8]=8 : ans = 24 -- If [1][7]=6 is deleted, 289 answers will be found.