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.
Scope (what is not claimed)
No new theorem or law is claimed: Trémaux’s method of solving a maze by marking passages walked (described by Lucas), the fact that it always arrives and walks each passage at most twice, and the fact that it has the same form as depth-first search are all known. No real maze is treated: the mazes are random $15\times15$ cell mazes and correspond to no garden or building maze. No race is run: the shortest path length is counted only for comparison with the steps; racing against methods that find the shortest path with a map is not the subject. Unmarkable cases and three dimensions are not treated: marks that fade, several walkers, and solid mazes are not treated. Relation to earlier papers: Paper 876, in its scope note, did not enter other ways of solving and did not treat methods other than wall-following, such as marking the passages walked; this paper sits in that seat (no earlier occupant). Paper 876 showed that keeping a hand on the wall always reaches the goal only when the walls are all joined to the outer wall. Here the fraction of arrivals by the right-hand rule is counted in mazes with loops and set beside the marking method. What is added: the arrival fractions of both methods in three kinds of maze with different loop fractions, a numerical check that Trémaux’s steps do not exceed twice the number of passages, a comparison of the steps with the shortest path, and placing the separator on “memory left in the maze, or only the wall direction carried along”.
1. Notation and the Question
Mazes: on $15\times15$ cells, a maze without loops (exactly one path between any two cells) is made by random digging, and $0$, $5$ or $15$ percent of the remaining inner walls are removed at random to add loops. $300$ mazes of each kind. Each opening between two adjacent cells counts as one passage. Start and goal are placed at random in different cells at least $3$ cells in from the outer wall.
Right-hand rule: step in the first open direction in the order right, forward, left, back. Arriving at the same cell with the same direction twice counts as circling forever, a failure.
Trémaux’s method: put one mark on each passage walked. (1) If a new passage leads to a cell visited before, walk back along it. (2) Otherwise choose an unmarked passage if there is one (at random). (3) If not, choose a passage with one mark. Passages with two marks are never walked.
Question: in mazes with loops, how does the marking method differ from the right-hand rule, and how many steps does it take?
2. Fraction That Arrive
Computation 2.1: fraction arriving, $300$ mazes each.
| fraction of walls removed | right-hand rule | Trémaux’s method |
|---|---|---|
| $0$ (no loops) | $1.000000$ | $1.000000$ |
| $5$ percent | $\mathbf{0.580000}$ | $1.000000$ |
| $15$ percent | $\mathbf{0.230000}$ | $1.000000$ |
Observation 2.2 with loops, the right-hand rule fails more often, and Trémaux’s method always arrived. In mazes without loops, the right-hand rule too arrived in all $300$: removing $5$ percent of walls dropped its arrival fraction to $0.580000$, and $15$ percent to $0.230000$. Why the right-hand rule failed in each maze (the condition shown in Paper 876, whether the walls are joined to the outer wall) was not counted here.
3. Steps
Computation 3.1: steps of Trémaux’s method.
| fraction of walls removed | largest steps / (twice passages) | mean steps / shortest path |
|---|---|---|
| $0$ (no loops) | $0.991071$ | $9.194842$ |
| $5$ percent | $0.997854$ | $\mathbf{20.042473}$ |
| $15$ percent | $0.982213$ | $21.898249$ |
Observation 3.2 the steps never exceeded twice the number of passages, but were far longer than the shortest path. In all $900$ mazes of the three kinds, the steps were at most twice the number of passages; since each passage is walked at most twice, this is a bound that follows from the rule: compared with the shortest path, it walked $9.194842$ times as far on average without loops, and $20.042473$ and $21.898249$ times with loops.
4. The Separator
Observation 4.1 the separator is whether memory is left in the maze or only the wall direction is carried along. The right-hand rule carries only the current cell and direction and leaves nothing in the maze: Trémaux’s method writes into the maze itself which passages have been walked and how often, and never walks a passage a third time. With that memory it arrived in all $900$ mazes, loops or not, and its steps stopped at twice the number of passages.
Observation 4.2 what is not said. Real mazes, racing against methods that find the shortest path with a map, marks that fade, several walkers and solid mazes are not treated. What is shown is that in the same mazes the marking method always arrived with steps within twice the number of passages, while the right-hand rule arrived less often as loops increased.
5. Roll Call and Closing
- rules of the right-hand rule and Trémaux’s method (Section 1): what is carried and what is written down.
- both $1.000000$ without loops (Computation 2.1): both arrive.
- right-hand rule $\mathbf{0.580000}$ and $\mathbf{0.230000}$ (Computation 2.1): fails more often with loops.
- largest ratio to twice $0.997854$ (Computation 3.1): never exceeds twice the passages.
- $\mathbf{20.042473}$ times the shortest (Computation 3.1): arrives, but not by a short way.
- left in the maze, or carried along (Observation 4.1): the separator; the scope note of Paper 876.
Closing: Marking the passages you walk always reaches the goal even with loops, in no more than twice the number of passages. In $15\times15$ mazes without loops, both the right-hand rule and Trémaux’s method always arrived: removing $5$ and $15$ percent of the remaining walls dropped the right-hand rule’s arrival fraction to $0.580000$ and $0.230000$, while Trémaux’s method stayed at $1.000000$, with steps at most twice the number of passages and $20.042473$ and $21.898249$ times the shortest path. The separator is whether memory is left in the maze or only the wall direction is carried along. Placed among the earlier papers, where Paper 876 showed the condition under which wall-following always arrives, here the right-hand rule’s arrival fraction was counted in mazes with loops and the marking method was set beside it. To be honest: the fastest way to solve a maze is not claimed. How arrival and steps change with where memory is kept, and no further.
References
- Even, S. (1979). Graph Algorithms. Computer Science Press.
- Lucas, É. (1882). Récréations mathématiques. Gauthier-Villars.
- Yamagishi, Y. (2026). Keeping a Hand on the Wall Always Reaches the Goal Only When the Walls Are All Joined to the Outer Wall [Paper 876]. YOI: https://www.yamagishiyuuki.com/yoi/876
Reference
Yamagishi, Y. (2026). Marking the Passages You Walk Always Reaches the Goal Even with Loops, in No More Than Twice the Number of Passages [Paper 941]. YOI: https://www.yamagishiyuuki.com/yoi/941
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 941. This paper is a preprint and has not been peer reviewed.