Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

右手を壁に付けて進む方法は、壁が外周と一続きでない迷路では同じところを回り続けることがある。本稿は、通った通路に印を付け、同じ通路を三度は通らない方法（トレモー法）を、ループの無い迷路とループを入れた迷路で右手法と比べ、着いた割合と歩数を数える。新しい定理も法則も主張しない。

第一に、ループの無い迷路では、どちらの方法も必ず着く。$15\times15$ の迷路 $300$ 個で、スタートとゴールを外周から $3$ ます以上内側に置くと、右手法もトレモー法も着いた割合は $1.000000$ だった（第2節）。

第二に、ループを入れると、右手法は着かないことが増える。残った壁の $5$ パーセントを外すと右手法の着いた割合は $\mathbf{0.580000}$、$15$ パーセントを外すと $\mathbf{0.230000}$ だった。トレモー法はどちらも $1.000000$ だった（第2節）。

第三に、トレモー法の歩数は、通路の数の二倍を超えなかった。歩数を通路の数の二倍で割った値の最大は、壁を外す割合 $0$・$5$・$15$ パーセントで $0.991071$・$0.997854$・$0.982213$ だった（第3節）。

第四に、必ず着くが、近道ではない。トレモー法の歩数を最短の道の長さで割った平均は、ループの無い迷路で $9.194842$、ループのある迷路で $\mathbf{20.042473}$・$21.898249$ だった（第3節）。

第五に、分離子は、覚えを迷路の側に残すか、壁の向きだけを持ち歩くかである。右手法が持っているのは、今いる場所と向きだけである。印は、どの通路を何度通ったかを迷路そのものに書き残し、同じ通路を三度通ることを禁じる（第4節）。

キーワード：トレモー法、迷路、右手法、深さ優先探索、通路の印、グラフの探索。

射程（何を示さないか）

新しい定理も法則も主張しない。通った通路に印を付けて迷路を解くトレモーの方法（リュカが紹介した）、それが必ず着き各通路を多くても二度しか通らないこと、それが深さ優先探索と同じ形であることは、いずれも既知である。実在の迷路を扱わない。迷路は乱数で作った $15\times15$ のますの迷路で、庭園や建物の迷路には対応しない。速さ比べをしない。最短の道の長さは歩数と比べるために数えただけで、地図を持って最短の道を探す方法との速さ比べは主題ではない。印を付けられない場合と三次元を扱わない。印が消える場合、複数の人が歩く場合、立体の迷路は扱わない。既刊との関係：論文876 の射程注記は、ほかの解き方に入らず、通った道に印を付ける方法など、壁伝い以外の解き方は扱わないと書いた。本稿はその席に座る（先客なし）。論文876 は、右手を壁に付けて進めば必ず着くのは、壁が外周と一続きのときだけであることを示した。ここでは、ループを入れた迷路で右手法の着く割合を数え、印を付ける方法と並べる。加えたのは、ループの割合を変えた三種類の迷路で二つの方法の着いた割合を出したこと、トレモー法の歩数が通路の数の二倍を超えないことを数で確かめたこと、歩数を最短の道と比べたこと、分離子を「覚えを迷路の側に残すか、壁の向きだけを持ち歩くか」に置いたことである。

1. 記法と問い

迷路：$15\times15$ のますで、乱数の穴掘りでループの無い迷路（どの二つのますの間にも道が一本だけ）を作り、残った内側の壁のうち $0$・$5$・$15$ パーセントを乱数で外してループを入れる。種類ごとに $300$ 個。隣り合う二つのますの間の開いた所を一本の通路と数える。スタートとゴールは、外周から $3$ ます以上内側の、別々のますに乱数で置く。

右手法：右・前・左・後ろの順に、最初に開いている向きへ一歩進む。同じますに同じ向きで二度来たら、回り続けるとみなして着かなかったと数える。

トレモー法：通った通路に印を一つずつ付ける。①初めての通路で、前に来たますに着いたら、来た通路を引き返す。②そうでなければ、印の無い通路があればそれを選ぶ（乱数）。③無ければ印が一つの通路を選ぶ。印が二つの通路は通らない。

問い：ループのある迷路で、印を付ける方法は右手法とどう違い、何歩かかるか。

2. 着いた割合

計算 2.1：迷路 $300$ 個ずつの着いた割合。

観察 2.2　ループを入れると右手法は着かないことが増え、トレモー法はすべて着いた。ループの無い迷路では、右手法も $300$ 個すべてで着いた。壁を $5$ パーセント外すと右手法の着いた割合は $0.580000$、$15$ パーセントでは $0.230000$ まで下がった。一つ一つの迷路で右手法が着かなかった理由（論文876 が示した、壁が外周と一続きかという条件）は、本稿では数えていない。

3. 歩数

計算 3.1：トレモー法の歩数。

観察 3.2　歩数は通路の数の二倍を超えなかったが、最短の道よりずっと長い。三種類の $900$ 個すべてで、歩数は通路の数の二倍以下だった。各通路を多くても二度しか通らないので、これは規則から出る上限である。最短の道に比べると、ループの無い迷路で平均 $9.194842$ 倍、ループのある迷路で $20.042473$ 倍・$21.898249$ 倍を歩いた。

4. 分離子

観察 4.1　分離子は、覚えを迷路の側に残すか、壁の向きだけを持ち歩くかである。右手法が持ち歩くのは、今いるますと向きだけで、迷路には何も残さない。トレモー法は、どの通路を何度通ったかを迷路そのものに書き残し、同じ通路を三度通らない。その覚えのおかげで、ループの有無にかかわらず $900$ 個すべてで着き、歩数は通路の数の二倍で止まった。

観察 4.2　言わないこと。実在の迷路、地図を持って最短の道を探す方法との速さ比べ、印が消える場合、複数の人が歩く場合、立体の迷路は扱わない。示したのは、同じ迷路で、印を付ける方法は必ず着いて歩数が通路の数の二倍に収まり、右手法はループが増えるほど着かなくなったことである。

5. 点呼と結び

1. 右手法とトレモー法の規則（第1節）：持ち歩くものと書き残すもの。
2. ループ無しでは両方 $1.000000$（計算 2.1）：どちらも着く。
3. 右手法 $\mathbf{0.580000}$・$\mathbf{0.230000}$（計算 2.1）：ループで着かないことが増える。
4. 二倍に対する最大 $0.997854$（計算 3.1）：通路の数の二倍を超えない。
5. 最短の $\mathbf{20.042473}$ 倍（計算 3.1）：着くが近道ではない。
6. 迷路の側に残すか、持ち歩くか（観察 4.1）：分離子・論文876 の射程注記。

結び：通った道に印を付ければループがあっても必ず着き、歩数は通路の数の二倍を超えない。$15\times15$ の迷路で、ループの無い迷路では右手法もトレモー法も必ず着いた。残った壁を $5$ パーセント・$15$ パーセント外すと、右手法の着いた割合は $0.580000$・$0.230000$ に下がり、トレモー法は $1.000000$ のままで、歩数は通路の数の二倍以下、最短の道の $20.042473$ 倍・$21.898249$ 倍だった。分離子は、覚えを迷路の側に残すか、壁の向きだけを持ち歩くかである。既刊との位置：論文876 が壁伝いで必ず着く条件を示したのに対し、ループを入れた迷路で右手法の着く割合を数え、印を付ける方法を並べた。正直に言えば、迷路をいちばん速く解く方法は言わない。覚えをどこに置くかで、着くかどうかと歩数がどう変わるか、そこまでである。

参考文献

1. Even, S. (1979). Graph Algorithms. Computer Science Press.
2. Lucas, É. (1882). Récréations mathématiques. Gauthier-Villars.
3. 山岸勇輝 (2026). 『右手を壁に付けて進めば必ず着くのは、壁が外周と一続きのときだけである』[論文876]. YOI: https://www.yamagishiyuuki.com/yoi/876

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「通った道に印を付ければループがあっても必ず着き、歩数は通路の数の二倍を超えない」［論文941］. YOI: https://www.yamagishiyuuki.com/yoi/941

@misc{yamagishi2026yoi941,
  author = {Yamagishi, Yuuki},
  title = {Marking the Passages You Walk Always Reaches the Goal Even with Loops, in No More Than Twice the Number of Passages},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/941},
  note = {Preprint, edition 1}
}