I often wonder: suppose I wake up one day and find myself in a maze of Hedges, like the one in "The Shining", what is the best strategy to get out of it? We can assume we have sunlight or a torch if its night time (or a full moon night).
I suppose there is some better option then running around randomly?
The standard algorithm is this:
Hold your hald on the right wall at all times and keep walking forward.
However, this only works in mazes where the exits are both on the outside and either you use it from the beginning or there are no disconnected parts.
Another one that works if you're allowed to use markings:
When you get to an unmarked junction, mark the path you entered by, then pick a random path. If you're going forward and you reach a junction wih a single mark somewhere, double mark that branch and turn back. If you reach a dead end, turn back and make a double mark. If you run out of possibilities, go back down the single marked path and add another mark on your way back. Treat all double marks as walls.
One of the most comprehensive answers to this question is given by William of Baskerville in Umberto Eco's book "The name of the rose" (page 188 of Mariner books edition, 2014):
"To find the way out of a labyrinth", William recited, "there is only one means. At every new junction, never seen before, the path we have taken will be marked with three signs. If, because of previous signs on some of the paths of the junction, you see that the junction has already been visited, you will make only one mark on the path you have taken. If all the apertures have already been marked, then you must retrace your steps. But if one or two apertures of the junction are still without signs, you will choose any one, making two signs on it. Proceeding through an aperture that bears only one sign, you will make two more, so that now the aperture bears three. All the parts of the labyrinth must have been visited if, arriving at a junction, you never take a passage with three signs, unless none of the other passages is now without signs."
"How do you know that? Are you an expert on labyrinths?"
"No, I am citing an ancient text I once read."
"And by observing this rule you get out?"
"Almost never, as far as I know. But we will try it, all the same.
And besides, within the next day or so I will have lenses and time to devote myself more to the books."
References:
