迷路パズルを自動生成するプログラム
図１のような迷路パズルを自動生成するプログラムを考えてみましょう。 入口と出
口は必ず一か所ずつなければなりません。 また、これらを繋ぐユニークな経路も必
要になります。
（図１、Ｆｕｎｃｔｉｏｎｖｉｅｗで作成）
まずは、格子点を作り、入口と出口となる場所を選び、そして、それらを結ぶユニー
クな経路を自動生成させることを考えます。 これを実行するプログラムは次のよう
になります。
以下に、 上のプログラムを使って求めた迷路用のユニークな経路を示します（図２
参照）。 青色の入口から赤色の出口まで経路は交差せずに繋がっています。迷路
の壁は黒い点を繋いで後で形成することになります。
＜入口→青、出口→赤＞
（図２、十進ＢＡＳＩＣによる２Ｄグラフィックス）
課題（その１）
特定の二点間を線で結ぶアルゴリズムは、電子工学などでの多くの応用が考えら
れます。 例えば、回路基板の設計時に使われる自動配線ソフトなどです。 以下の
制約のもとで動く配線ソフトの簡易版を作成してください。
（１）配線の総量を最小化する（寄生素子の影響の最小化）
（２）各配線の長さを等しくする（負荷の均一化）
それでは、壁を形成する為のプログラムを考えましょう。外壁は比較的簡単に形成
できます（図３参照）。入口と出口を除いた部分を壁として描画すれば良い訳です。
＜入口→青、出口→赤＞
（図３、十進ＢＡＳＩＣによる２Ｄグラフィックス）
内壁については、次の二つの方針に基づいて描画させます。
（１）内壁は経路と交差しない
（２）内壁は閉じた図形を形成しない
これらの条件を満たすように形成した内壁を図４に示します。
＜入口→青、出口→赤＞
（図４、十進ＢＡＳＩＣによる２Ｄグラフィックス）
外壁にある格子点から経路と交差しないように内壁を形成しています。 また、内壁
同士も連結しないようにしました。 上図を見れば判るように、 左上の部分に孤立し
た格子点が残っています。 残った点を内壁又は外壁に繋げる為のプログラムがさ
らに必要になります。
図５は孤立点を繋いだ後の図です。赤い三点が孤立点で、これらをピンクの線で他
の壁に繋いでいます。
＜入口→青、出口→赤＞
（図５、十進ＢＡＳＩＣによる２Ｄグラフィックス）
迷路パズルを自動生成する全体プログラムついては、以下のリンクを参考にしてく
ださい。
課題（その２）
迷路のサイズを面積で測って４倍になるようにプログラムを修正してください （図６
参照）。
＜入口→青、出口→赤＞
（図６、十進ＢＡＳＩＣによる２Ｄグラフィックス）
課題（その３）
上のプログラムでは、内壁は必ず外壁上の格子点からスタートしています。外壁と
は繋がっていない内壁を持つようにするには、 プログラムにどのようなコードを追
加しなければなりませんか。また、独立した内壁の存在と経路のユニークさの関係
を議論してください。
課題（その４）
三次元的な迷路パズルを作ってください。まずは、擬似的なものからスタートしても
構いません。