Abstract
Marking the passages you walk always reaches the goal even with loops, in no more than twice the number of passages (Paper 941). Only a single walker was treated there, and several walkers were not. In $15\times15$ mazes made as in Paper 941, this paper has 1, 2, 4 or 8 people start together and walk Tremaux’s method one step per turn, with marks shared by all or kept separately, and counts the turns until someone reaches the goal, over 400 mazes without loops and 400 with 15 percent of walls removed. No new theorem or law is claimed.
First, two walkers sharing marks arrived more than twice as fast as one: in mazes without loops the mean turns to arrival were $173.88$ for one walker and $78.41$ for two sharing marks, one over two being $\mathbf{2.217472}$. Two keeping marks separately took $126.48$ (Section 2).
Second, the gain from sharing shrank with more walkers and was gone at eight: in mazes without loops, separate over shared was $1.612976$ for two, $1.403499$ for four and $\mathbf{0.987638}$ for eight (Section 2).
Third, with more walkers the turns approach the shortest path length: against a mean shortest path of $41.67$, eight walkers sharing took $\mathbf{1.368468}$ times and eight keeping separately $1.351551$ times, and going from four to eight only cut $58.30$ to $57.03$ (Section 3).
Fourth, in mazes with loops a gain from sharing remained even with eight: with 15 percent of walls removed the mean shortest path was $12.78$; eight sharing took $2.563295$ times it, separate over shared was $1.112663$, and one over eight was $\mathbf{5.008396}$ (Section 3).
Fifth, the separator is whether the turns to arrival are set by how many passages remain unexplored or by the length of the shortest path: for every number of walkers and way of keeping marks all 400 mazes were solved, and no maze was solved faster than its shortest path. Eight walkers in mazes without loops stopped near the shortest path length, taking about the same turns whether marks were shared or not (Section 4).
Keywords: maze, Tremaux’s method, shared marks, several walkers, shortest path, search.
Scope (what is not claimed)
No new theorem or law is claimed: Tremaux’s method of solving mazes by marking passages walked, exploring mazes and graphs with several walkers, and that adding walkers does not keep raising search speed in proportion to their number, are treated in the study of search. These are set values: the mazes are random $15\times15$ grids made as in Paper 941; wall-removal shares of 0 and 15 percent, 400 mazes each, 1, 2, 4 and 8 walkers, and a cutoff of 4500 turns are set here. They correspond to no building search, swarm or robot. The walkers are not made clever: talking, dividing roles and knowing where others are are not included. Only the number of marks on passages is shared, and each walker follows the same Tremaux rule as when alone. Reasons are not measured: why two walkers are more than twice as fast, or why the gain vanishes at eight, is not counted. Only mean turns and shortest path lengths are set out. Relation to earlier papers: Paper 941, in its scope note, did not treat cases where marks cannot be made or three dimensions, leaving out fading marks, several walkers and three-dimensional mazes; this paper sits in the seat of several walkers (no earlier occupant; the fading-marks seat of the same scope note was taken by Paper 981). Paper 941 showed that marking the passages you walk always reaches the goal even with loops, in no more than twice the number of passages. Here the shortening of turns to arrival when several people walk by the same method is counted. Paper 981 showed that when marks fade, some mazes with loops are not solved. Here marks do not fade. What is added: counting turns to arrival over 400 mazes for four numbers of walkers and two ways of keeping marks, comparing with the shortest path length, measuring that the gain from sharing shrinks with the number of walkers, comparing mazes with and without loops, and placing the separator on “unexplored passages, or the shortest path”.
1. Notation and the Question
Mazes: as in Paper 941, a loop-free maze is dug at random on a $15\times15$ grid and 0 or 15 percent of the remaining inner walls are removed at random; 400 of each kind. The mean number of passages is $224.0$ and $253.0$, and the mean shortest path from start to goal is $41.67$ (median $35.0$) and $12.78$ (median $11.0$). Start and goal are placed at least 3 cells inside the outer wall.
Walking: $k$ walkers stand at the same start and, each turn, take one step in order by the Tremaux method of Paper 941 (arriving at a junction by a new passage when other passages are marked, turn back; otherwise pick an unmarked passage at random, or if none a passage marked once, adding one mark each time a passage is walked). With shared marks all walkers count and add to the same marks; with separate marks each counts only its own. The turn at which someone reaches the goal is counted, the cutoff is 4500 turns, and each maze has its own random seed.
Question: when several people walk sharing marks, how much do the turns to arrival shrink, and how does that change with the number of walkers and the shape of the maze?
2. Mazes Without Loops
Computation 2.1: turns to arrival over 400 mazes (all arrived).
| walkers | marks | mean | median | over mean shortest path | one over this number |
|---|---|---|---|---|---|
| $1$ | alone | $173.88$ | $161.5$ | $4.172476$ | none |
| $2$ | shared | $78.41$ | $65.5$ | $1.881637$ | $\mathbf{2.217472}$ |
| $2$ | separate | $126.48$ | $101.0$ | $3.035035$ | none |
| $4$ | shared | $58.30$ | $44.5$ | $1.399064$ | $2.982334$ |
| $4$ | separate | $81.83$ | $61.0$ | $1.963585$ | none |
| $8$ | shared | $57.03$ | $42.0$ | $\mathbf{1.368468}$ | $3.049011$ |
| $8$ | separate | $56.32$ | $42.0$ | $1.351551$ | none |
Separate over shared (means) was $1.612976$ for two, $1.403499$ for four and $0.987638$ for eight.
Observation 2.2 the gain from sharing was largest for two and gone at eight. Two sharing were $2.217472$ times faster than one and $1.612976$ times faster than two keeping marks separately: with eight, sharing and keeping separately gave means of $57.03$ and $56.32$ and the same median $42.0$. Why two became more than twice as fast as one is not counted here.
3. The Shortest Path and Mazes with Loops
Computation 3.1: mazes with 15 percent of walls removed (all arrived).
| walkers | marks | mean | median | over mean shortest path | one over this number |
|---|---|---|---|---|---|
| $1$ | alone | $164.04$ | $136.5$ | $12.837996$ | none |
| $2$ | shared | $84.63$ | $75.5$ | $6.623166$ | $1.938347$ |
| $2$ | separate | $109.14$ | $82.5$ | $8.541773$ | none |
| $4$ | shared | $48.54$ | $37.0$ | $3.798670$ | $3.379603$ |
| $4$ | separate | $59.34$ | $43.0$ | $4.644297$ | none |
| $8$ | shared | $32.75$ | $24.0$ | $\mathbf{2.563295}$ | $\mathbf{5.008396}$ |
| $8$ | separate | $36.44$ | $27.0$ | $2.852084$ | none |
Separate over shared was $1.289681$ for two, $1.222611$ for four and $1.112663$ for eight.
Observation 3.2 more walkers bring the turns near the shortest path length, and in mazes with loops they remain far from it. Eight walkers in mazes without loops took $1.368468$ times the shortest path, hardly less than the $1.399064$ times for four: in mazes with loops the shortest path was short at $12.78$, eight still took $2.563295$ times it, a gain from sharing remained ($1.112663$), and one over eight was $5.008396$.
4. The Separator
Observation 4.1 the separator is whether the turns to arrival are set by how many passages remain unexplored or by the length of the shortest path. In both kinds of maze, for every number of walkers and way of keeping marks, all 400 mazes were solved, and in no maze was the goal reached faster than its shortest path: the shortest path length is a lower bound on turns however many walk. Eight walkers in mazes without loops came near $1.368468$ times that bound and took the same turns however marks were kept. While walkers were few, sharing shortened the turns.
Observation 4.2 what is not said. More than eight walkers, talking or dividing roles, knowing where others are, fading marks (Paper 981), three-dimensional mazes, real searches or robots, and why two are more than twice as fast are not treated. What is shown is how the gain from sharing marks changes with the number of walkers and the shape of the maze when several people walk the same Tremaux method.
5. Roll Call and Closing
- Tremaux’s method for several walkers (Section 1): marks shared or kept separately.
- two sharing are $\mathbf{2.217472}$ times faster than one (Computation 2.1): more than twice.
- separate over shared $\mathbf{0.987638}$ at eight (Computation 2.1): the gain is gone.
- eight take $\mathbf{1.368468}$ times the shortest path (Computation 2.1): near the lower bound.
- with loops, one over eight $\mathbf{5.008396}$ and $\mathbf{2.563295}$ times the shortest path (Computation 3.1): a gain remains.
- unexplored passages, or the shortest path (Observation 4.1): the separator; the scope note of Paper 941.
Closing: Sharing marks in a maze without loops, two walkers arrive more than twice as fast, but with eight the gain is gone. When several people walk Tremaux’s method in the mazes of Paper 941, two sharing marks in mazes without loops were $2.217472$ times faster than one and $1.612976$ times faster than two keeping marks separately: with eight, separate over shared became $0.987638$ and the turns stopped near $1.368468$ times the shortest path. In mazes with loops eight still took $2.563295$ times the shortest path, and a gain from sharing remained. The separator is whether the turns to arrival are set by how many passages remain unexplored or by the length of the shortest path. Placed among the earlier papers: to the Tremaux method Paper 941 counted for one walker, the several walkers Paper 941 did not treat were added. Fading marks from the same scope note were counted in Paper 981. To be honest. This is a model of walkers who do not talk and share only numbers of marks, counting turns to arrival. Reasons are not counted. How the gain from sharing changes with the number of walkers and the shape of the maze, and no further.
References
- Lucas, É. (1882). Récréations mathématiques. Gauthier-Villars.
- 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
- Yamagishi, Y. (2026). When Marks Fade, a Maze Without Loops Only Takes Longer, but with Loops Some Goals Are Not Reached [Paper 981]. YOI: https://www.yamagishiyuuki.com/yoi/981
Reference
Yamagishi, Y. (2026). Sharing Marks in a Maze Without Loops, Two Walkers Arrive More Than Twice as Fast, but with Eight the Gain Is Gone [Paper 985]. YOI: https://www.yamagishiyuuki.com/yoi/985
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 985. This paper is a preprint and has not been peer reviewed.