Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文941 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/941 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。

本文はサイトの記事でも読めます（2026年10月12日 18:20 に公開します）。

@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}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969451・969456・969461・969490 に記録されました（2026年10月01日 23:00（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

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

第一に、ループの無い迷路では、どちらの方法も必ず着く。$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節）。

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

Abstract

Keeping the right hand on the wall can circle the same place forever in a maze whose walls are not all joined to the outer wall.This paper compares the method of marking each passage walked and never walking a passage a third time (Trémaux’s method) with the right-hand rule, in mazes without loops and mazes with loops added, counting the fraction that reach the goal and the number of steps.No new theorem or law is claimed.

First, in mazes without loops, both methods always arrive: in $300$ mazes of $15\times15$ cells, with start and goal placed at least $3$ cells in from the outer wall, both the right-hand rule and Trémaux’s method arrived with fraction $1.000000$ (Section 2).

Second, with loops added, the right-hand rule fails more often: removing $5$ percent of the remaining walls, the right-hand rule arrived with fraction $\mathbf{0.580000}$, and removing $15$ percent, $\mathbf{0.230000}$. Trémaux’s method arrived with $1.000000$ in both (Section 2).

Third, Trémaux’s steps never exceeded twice the number of passages: the largest ratio of steps to twice the number of passages was $0.991071$, $0.997854$ and $0.982213$ for $0$, $5$ and $15$ percent of walls removed (Section 3).

Fourth, it always arrives, but not by a short way: the mean ratio of Trémaux’s steps to the shortest path length was $9.194842$ in mazes without loops and $\mathbf{20.042473}$ and $21.898249$ in mazes with loops (Section 3).

Fifth, the separator is whether memory is left in the maze or only the wall direction is carried along: the right-hand rule holds only the current position and direction. Marks write into the maze itself which passages have been walked and how often, and forbid walking a passage a third time (Section 4).

Keywords: Trémaux’s method, maze, right-hand rule, depth-first search, passage marks, graph exploration

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/941/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/941 はいつも最新の版を指します）。

YOI の一覧へ