総合コミュニケーション科学 (高田)


プロジェクトの目標

ここでは、計算機に問題を解かせる方法を習得することを目標として、 パズルを解くプログラムを作ってみることにします。

パズルにもいろいろなものがありますが、 ここでは古典的な テトロミノ・ペントミノ に 挑戦してみたいと思います。

計算機に試行錯誤を行なわせる方法をマスターして頂くのがねらいです。

すべての解を、できるだけ重複すること無く数え上げる方法を、 さらに短時間で回答を得られるようにする方法を、考えてみましょう。

プレゼンテーション

最後の回にチームごとにプロジェクトの発表をお願いします。

進行上でのおねがい

連絡事項

特にありません。

講義資料

以下のプログラムなどは 無保証 です。 特に、 想定外の入力などの例外的状況に関して、 このままでは問題を起こす可能性もあります。 本講義のレポートに利用する目的に限っては、 ここに示すプログラムをそのまま無批判に利用しても構いませんが、 それ以外の用途に用いることを想定できる場合には 必ず各自のリスク評価を行なった上で、修正利用してください。

注意: これらのプログラム・コードは、電気通信大学学内からのみ参照可能です。
permitation.c 順列を生成するプログラム
permitation N とすると、 1 から N までの数の順列を生成する。 いろいろな組み合わせの問題を解く時の基本的な要素を含んでいる。 問題が単純な場合のプログラミング例。
FindPath.c ネットワーク中のパスを探すプログラム
汎用のプログラムを使って、農夫と狼と山羊とキャベツのパズルを解いている。 問題の定義とその解析はこちらを参照のこと。 また、実行結果をこちら、 この時使った入力データをこちらに示す。
EightQueens.c 8-Queen の問題を解くプログラム
8 × 8 のチェスの盤の上に、 8 つのクィーンを互いに取り合わないように配置する問題。 クィーンは将棋の飛車と角をあわせた動きで、 9 個以上は置けないのは自明である。 実行時に -m オプションを付けると盤面の見取り図を出力することができる。 実行結果をこちらに示す。 問題が少し複雑になった場合のプログラミング例。
tetromino.c テトロミノを解くプログラム
パズルゲームを解くプログラム。 メーカーのホームページには 783 通りの解があるとのことだが、 このプログラムからは重複・対称・回転などを除いていないので 3000 通り以上の答えが出てきている。 その実行結果をこちらに示す。
pentomino.c ペントミノを解くプログラム
パズルゲームを解くプログラム。これは重複・対称・回転などを取り除いていない。 答えの総数は 9356 個。 結果をこちらに示す。 このとき実行にかかった時間は 540 秒程度だが、最適化すれば 110 秒程度に短縮できる。
また重複を取り除いた場合の実行可能プログラムその結果とを示す。 この場合のソースコードはいまのところ非公開。 メーカーのホームページによれば 2339 通りの解があるとのこと。 答えの数はメーカーの公表値と一致している。 なお、実行にかかった時間は 55 秒程度。

これらのプログラムは、 情報基盤センター情報処理教育用システム (sol.edu.cc.uec.ac.jp) の Linux 環境で gcc コンパイラ バージョン 4.8.2 (/opt2/gcc/4.8.2/bin/gcc) を利用して 動作を確認しています。 これ以外の OS 環境での動作は確認もしくは保証していません。

関連資料


takata@cc.uec.ac.jp