課題4 迷路やパズルを解く
注意
概要
迷路、スケルトン (クロスワードパズルの一種)、イラストロジックなど、
理詰めで解けるパズルを解くプログラムを作る。
日程
- 第1週目: 説明会。
- 第2週目: 課題の取り組み。計画書提出。
- 第3週目: 課題の取り組み。
- 第4週目: 課題の取り組み。
- 第5週目: 課題の取り組み。
- 第6週目: まとめ。レポート提出。
- 第7週目: 発表会。
課題の進め方
- 解くべき課題を決める
1人で1課題に取り組むものとする。
各自で何を解くのかを考える。
インターネットで検索すると、いろいろなパズルが見つかるので、参考になる。
また、書店にもパズルの本がいろいろある。
- 計画を立て、報告する
選んだ課題、解決方法の指針、実施計画をA4で1〜2ページにまとめて報告する。
- アルゴリズムを考える
人間ならどうやって解くのかを考え、フローチャートや箇条書などにしてみる。
- データ構造を考える
- アルゴリズムを計算機向けに直す
- アルゴリズムを検証する
上記データ構造とアルゴリズムに基づいて、自分で簡単な問題を解いてみる。
- プログラムを書く
- 動作させてみる
パズルの例
- 迷路
- スケルトン (クロスワードパズルの一種)
埋めるべき単語の一覧を与えて、文字数を頼りに埋めていくタイプ
- イラストロジックの類
- スリザーリンク
- その他いろいろ
(ニコリのパズル)
迷路の難易度
- レベル1: 単純な迷路を通過できれば良い
左右の壁と、そこから延びた枝しかない迷路 → 壁伝いで通過
サンプルのmaze1.dat, maze2.dat
- レベル2: レベル1の最短経路を求める
袋小路を消去する
- レベル3: ゴールが中央にある、ループがある、などを通過できれば良い
「壁伝い」では出られない
サンプルのmaze3.dat
- レベル4: レベル3の最短経路を求める
「無駄なループ」も消去
- レベル5: 立体交差がある迷路を通過できれば良い
- レベル6: レベル5の最短経路を求める
レポートについて
卒論等はLaTeXで書くことが多いので、
LaTeXで書くことを強く勧める。
発表について
コンピュータを用いることを強く勧める。
MagicPoint (UNIX), PowerPoint (Windows) などが使える。
サンプルプログラム
その他の情報
(作成: 2002年4月11日, 最終更新: 2003年5月16日)