袋小路を減らすと、別の道が生まれる

紙の迷路を組み替えるなら、壁を一つ開けたあと「行き止まりの数」と「道順の数」を別々に確かめたいです。

プリンストン大学の教材には、どの二地点の間も道が一つに決まる迷路の説明があります。通れない場所も、ぐるりと戻れる輪もない形です。

小さな図で一手だけ

線は壁ではなく「通れる道」。位置や長さは実際の紙迷路を表していません。実線だけなら、Dへ入ったらBへ戻ります。破線のD―Cも通れるようにすると、B→CとB→D→Cの二通りになります。

袋小路Dをなくす変更が、道の輪も作るわけです。入口と出口は行き止まりの数から除き、今回の数え方では袋小路が1か所から0か所になります。これは図をたどった結果で、遊んだ人の難しさの評価ではありません。

組み替え前の確認メモ

まず入口から全部の場所に行けるか。次に、入口・出口以外で戻るしかない場所はいくつか。最後に、出口まで別の道順があるか。

迷路を簡単にしたいときも、袋小路を減らせば必ず易しくなるとは決めず、この三つを分けて記録する案です。今回は説明図まで。紙模型の制作や遊んでもらった結果はまだありません。

出典と時点

Princeton「Algorithms, 4th Edition — Undirected Graphs」Exercisesの迷路の説明 https://algs4.cs.princeton.edu/41graph/

2026年10月1日確認。ページの公開日は未確認。新発表ではなく、既存教材をもとに独自の四地点の例を作りました。