Abstract
Marking the passages you walk always reaches the goal even with loops, in no more than twice the number of passages (Paper 941). Marks that fade were not treated there. In $15\times15$ mazes made as in Paper 941, this paper gives the marks of Tremaux’s method a lifetime in steps and ignores older marks, and counts how the share of mazes solved and the number of steps change, over 400 mazes without loops and 400 with 15 percent of walls removed. No new theorem or law is claimed.
First, in mazes without loops, fading marks only made the walk longer: even with the lifetime cut to $\mathbf{0.0893}$ of the number of passages (20 steps), all 400 were solved, with $\mathbf{1.461064}$ times the steps of marks that never fade (Section 2).
Second, with loops, some mazes were not solved: with 15 percent of walls removed, a lifetime of $\mathbf{0.7905}$ of the number of passages (200 steps) gave a solved share of $0.9925$, and 20 steps gave $\mathbf{0.9625}$ (Section 2).
Third, a cutoff four times longer did not reduce the unsolved mazes: raising the cutoff from 4500 to 18000 steps left the solved shares in mazes with loops at $0.9925$, $0.9950$, $0.9900$ and $0.9625$ for lifetimes of 200, 100, 50 and 20 steps (Section 3).
Fourth, a lifetime of 1 step matched a random walk without marks, which reached the goal given time: the solved shares for a 1-step lifetime and the random walk were $0.5225$ and $0.5175$, $0.9150$ and $0.9175$; at 18000 steps the 1-step lifetime reached $\mathbf{1.0000}$ in mazes with loops, above the $0.9625$ of a 20-step lifetime (Section 3).
Fifth, the separator is not whether the lifetime is short compared with the number of passages but whether the maze has loops: mazes without loops were all solved with lifetime $0.0893$ of the number of passages, while mazes with loops had unsolved cases at $0.7905$ (Section 4).
Keywords: maze, Tremaux’s method, mark lifetime, random walk, loop, cutoff.
Scope (what is not claimed)
No new theorem or law is claimed: Tremaux’s method of solving a maze by marking passages walked, that it always reaches the goal, and that a random walk without marks eventually reaches the goal in a connected finite maze, are all known. 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, mark lifetimes from 1 to 1000 steps, and cutoffs of 4500 and 18000 steps are set here. They correspond to no garden or building maze, nor to trails left by animals. The mechanism is not measured. What the walker kept doing in unsolved mazes is not counted. Only whether the goal was reached and the number of steps are counted. Nothing is said about forever: unsolved means unsolved within 18000 steps; it is not claimed that walking longer would never reach the goal. 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 fading marks (no earlier occupant). 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 change in the solved share and steps when those marks fade after a set number of steps is counted. What is added: counting solved shares and steps over 400 mazes for two kinds of maze and eight lifetimes, confirming that a cutoff four times longer does not change the solved share, setting a 1-step lifetime beside a random walk without marks, and placing the separator on “not how short the lifetime is, but whether there are loops”.
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 (open places between neighbouring cells) is $224.0$ for 0 percent and $253.0$ for 15 percent. Start and goal are placed in different cells at least 3 cells inside the outer wall.
Walking: with Tremaux’s method as in Paper 941, each passage walked records the step number as a mark. With a mark lifetime of $\ell$ steps, marks made $\ell$ or more steps before now are not counted (with no $\ell$, marks never fade). Arriving at a junction by a new passage when other passages there are marked, the walker turns back; otherwise it picks an unmarked passage at random, or if none, a passage marked once. Lifetimes are never, 1000, 400, 200, 100, 50, 20 and 1 steps, the cutoff is $4500$ steps (20 times the 225 cells), and each maze has its own random seed. For comparison, a random walk picking a neighbouring passage at random without marks was also run.
Question: when marks fade, how do the solved share and the number of steps change, and how does that differ with the shape of the maze?
2. Solved Share and Steps
Computation 2.1: share of 400 mazes solved and mean steps in solved runs (cutoff 4500 steps).
| lifetime | no loops: share | steps | 15 percent: share | steps | lifetime over passages (none / 15) |
|---|---|---|---|---|---|
| never | $1.0000$ | $162.3$ | $1.0000$ | $152.7$ | none |
| 1000 steps | $1.0000$ | $162.3$ | $1.0000$ | $152.7$ | $4.4643$ / $3.9526$ |
| 400 steps | $1.0000$ | $162.3$ | $1.0000$ | $155.4$ | $1.7857$ / $1.5810$ |
| 200 steps | $1.0000$ | $167.2$ | $0.9925$ | $173.1$ | $0.8929$ / $\mathbf{0.7905}$ |
| 100 steps | $1.0000$ | $183.0$ | $0.9950$ | $196.6$ | $0.4464$ / $0.3953$ |
| 50 steps | $1.0000$ | $197.8$ | $0.9900$ | $185.0$ | $0.2232$ / $0.1976$ |
| 20 steps | $1.0000$ | $237.1$ | $\mathbf{0.9625}$ | $219.6$ | $\mathbf{0.0893}$ / $0.0791$ |
| 1 step | $0.5225$ | $1301.7$ | $0.9150$ | $1113.9$ | $0.0045$ / $0.0040$ |
| random walk | $0.5175$ | none | $0.9175$ | none | none |
Dividing steps in solved runs by those with marks that never fade gave, for lifetimes of 200, 100, 50 and 20 steps, $1.030446$, $1.128132$, $1.219007$ and $\mathbf{1.461064}$ without loops and $1.133345$, $1.286930$, $1.211056$ and $1.438104$ with 15 percent.
Observation 2.2 in mazes without loops, fading marks only made the walk longer. All 400 were solved down to a lifetime of 20 steps ($0.0893$ of the number of passages): steps rose as the lifetime was cut below 400 steps. Steps for the 15-percent mazes are means over solved runs only, so the value $1.211056$ at 50 steps being below $1.286930$ at 100 steps includes the effect of leaving out unsolved mazes.
Observation 2.3 with loops, some mazes were not solved. With 15 percent of walls removed, all were solved up to a lifetime of 400 steps ($1.5810$), and 200 steps ($0.7905$) gave $0.9925$: 20 steps gave a share of $0.9625$ solved within 4500 steps.
3. A Longer Cutoff
Computation 3.1: the same mazes and seeds were recounted with the cutoff raised four times to 18000 steps. With the same seeds the walk up to 4500 steps is identical, so the solved share cannot fall.
| lifetime | no loops 4500 steps | no loops 18000 steps | 15 percent 4500 steps | 15 percent 18000 steps |
|---|---|---|---|---|
| 200 steps | $1.0000$ | $1.0000$ | $0.9925$ | $0.9925$ |
| 100 steps | $1.0000$ | $1.0000$ | $0.9950$ | $0.9950$ |
| 50 steps | $1.0000$ | $1.0000$ | $0.9900$ | $0.9900$ |
| 20 steps | $1.0000$ | $1.0000$ | $0.9625$ | $0.9625$ |
| 1 step | $0.5225$ | $0.8700$ | $0.9150$ | $\mathbf{1.0000}$ |
Observation 3.2 mazes with loops that were not solved stayed unsolved with a cutoff four times longer. The shares for lifetimes of 200, 100, 50 and 20 steps did not change at 18000 steps: a 1-step lifetime, by contrast, solved all 400 mazes with loops and $0.8700$ of those without loops at 18000 steps. Walking beyond 18000 steps was not counted.
Observation 3.3 a 1-step lifetime gave the same share as a random walk without marks. With a 1-step lifetime no mark counts by the time the next cell is reached, so the turn-back rule never acts and a neighbouring passage is picked at random: the solved shares were $0.5225$ against $0.5175$ and $0.9150$ against $0.9175$ for the random walk, within 0.05 (random numbers are used differently, so the values are not identical).
4. The Separator
Observation 4.1 the separator is not whether the lifetime is short compared with the number of passages but whether the maze has loops. Mazes without loops were all solved with a lifetime of $0.0893$ of the number of passages, while mazes with loops had unsolved cases at $0.7905$: for similar ratios of lifetime to passages, the solved share split by whether loops were present. What the walker kept doing in unsolved mazes is not counted here.
Observation 4.2 what is not said. The solved share when walking beyond 18000 steps, the mechanism of failure, several walkers, three-dimensional mazes, trails left by animals, and real mazes are not treated. What is shown is how the solved share and steps change as the mark lifetime shortens, in two kinds of random maze.
5. Roll Call and Closing
- Tremaux’s method with mark lifetimes (Section 1): older marks are not counted.
- without loops, all solved down to $\mathbf{0.0893}$ of the passages (Computation 2.1): steps $\mathbf{1.461064}$ times.
- with loops, 0.9925 at $\mathbf{0.7905}$ and $\mathbf{0.9625}$ at 20 steps (Computation 2.1): some mazes unsolved.
- the same shares at 18000 steps (Computation 3.1): a longer cutoff does not reduce them.
- a 1-step lifetime matches a random walk, reaching $\mathbf{1.0000}$ at 18000 steps (Computation 3.1): solved given time.
- whether there are loops (Observation 4.1): the separator; the scope note of Paper 941.
Closing: When marks fade, a maze without loops only takes longer, but with loops some goals are not reached. Giving the marks of Tremaux’s method a lifetime in mazes made as in Paper 941, all 400 mazes without loops were solved even at $0.0893$ of the number of passages, with $1.461064$ times the steps: with 15 percent of walls removed the solved share was $0.9925$ at $0.7905$ and $0.9625$ at 20 steps, unchanged with an 18000-step cutoff. A 1-step lifetime, the same as a random walk without marks, solved all mazes with loops within 18000 steps. The separator is not whether the lifetime is short compared with the number of passages but whether the maze has loops. Placed among the earlier papers: to the solved share and steps Paper 941 counted with marks that never fade, the mark lifetime Paper 941 did not treat was added. To be honest. This counts whether goals were reached within 18000 steps and the number of steps in two kinds of random maze. The mechanism of failure is not counted. What happens when mark lifetimes shorten, 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
Reference
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
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 981. This paper is a preprint and has not been peer reviewed.