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

課題の提出

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

課題５

• ★必修：課題５Ａ★

  授業中に説明したナンプレ(或いはSudoku^TM)のアルゴリズムの要点をもとに、ナンプレの解答を求めるプログラムを作成せよ。
  ・問題ファイルからナンプレの９ｘ９のマスの状態を読み込む部分には、こちらで用意したsudoku-frame.cを用いてよい。
  ・問題ファイルでは、空欄を0で表記するものとする。
  ・問題を解く部分はmain()関数の中に直接記述せず、必ずmain()関数から別の関数を呼ぶ形で作成すること。
  ・課題５Ａに関しては、１つめの解が得られた時点でプログラムを停止してよい（複数の解を探索する必要はない）。
  ・実行した結果得られる、解・解を得るのにかかった探索数・実行時間（ミリ秒程度の精度）を標準出力に読みやすい形で出力すること。

  参考：unix(linux)で実時間で実行時間を計測するプログラム例(gettimeofday関数を利用)
  
  プログラム内で実行時間を計測したい場合の参考にしてください（他の手段でも構いませんが、ミリ秒オーダーの精度で計測できること）。

  問題	サンプル1	サンプル2
  出展	Extreme SudokuoのEvilレベルより	Sudokuサイトの上級++より
  問題ファイル	quiz-sample1.txt	quiz-sample2.txt
  問題	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])

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

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

  • 提出物 必須〔5A-2〕：サンプル１の解、探索数、実行時間を保存したテキストファイル
    quiz-sample1.txtに対して実行した結果得られる、解・そのときの探索数・実行時間を保存したテキストファイル。
    ５階計算機室のコンピュータで実行した場合は、使用したCPUの型・クロック数、および実行環境も追記すること。
    

• ★必修：課題５Ｂ★

  2012/6/19の授業において説明した、ナップサック問題の解を、最長経路問題を解くアルゴリズムから得る方法について、授業で説明したグラフをもとに説明せよ。
  ・もとのナップサック問題の例題は、(value,weight) = {(11,7),(3,2),(9,5),(13,8),(5,3)}, 重量制限は10とするものである。
  ・最長経路問題に変換したグラフを遺漏なく作図すること。
  ・グラフの辺は、３種類に分けて用意し、説明の時に区別がつくようにしておくこと。
  ・グラフの辺の重みは（０も含め）必ず明示すること。（ここでいう辺の重みはナップサック問題のweightではない）
  ・最長経路とその値を、グラフ上でも、解答として文章でも、両方で示すこと。
  ・【重要】グラフ構造のどこがナップサック問題の解の探索のどの部分に対応するか説明せよ。
  ・【重要】特に、ある頂点から辺が２つ出ていく場合と１つしか出て行かない場合に注意して説明すること。
  ・【重要】特に、授業中に示したグラフレイアウトにおいて、グラフ中の上方と右方への移動が何を意味するか説明すること。

  • 提出物 必須〔5B-1〕：解答を記述したpdfファイル
    先頭に「２０１２年度データ構造とアルゴリズム課題５Ｂ」と学籍番号、氏名を明記すること。
    本課題に関しては説明文が似ている場合は強い減点対象になるので注意すること（説明の構造自体が似るのは構わない）。

• ◆発展：課題５Ｘ◆

  ナンプレの亜種として、以下の「対角線」「６ｘ６」の２つを考える。 (wikipediaの説明)
  それぞれ、課題５Ａのプログラムにおけるバックトラックの条件式をどのように変更することで対応が可能か、説明せよ。
  必要であれば疑似プログラムコード（アルゴリズムの進行が疑念なく理解できるレベル）を用いてよい。（Ｃ言語による実装まではしなくともよい）

  「対角線」縦横な3×3のブロックの他に、対角線にも全ての数字が揃うようにしなければならない問題。
  「６ｘ６」９ｘ９の標準問題ではでは３ｘ３ブロックが９個用意され、数字が９種使われるが、そのかわりに２ｘ３のブロックを６個用意し、数字も１〜６の６種のみとする問題。

  • 提出物 必須〔5X-1〕：解答を記述したpdfファイル
    先頭に「２０１２年度データ構造とアルゴリズム課題５Ｘ」と学籍番号、氏名を明記すること。
    「対角線」「６ｘ６」それぞれについて、解答を示すこと。片方のみの解答も認める。
    疑似コードではあるが、相談した場合、教えた・教わったの関係を本課題では認めるので、これまでの例に沿って、当該関係を示すこと。