How to construct a maximally difficult NxN labyrinth ?

This question is just for fun; I don't know if it has a nontrivial answer. Let $\Gamma$ be an $n\times n$ square grid, thought of as a graph where the edges of the graph are the edges of the squares of the grid and the vertices of the graph are the vertices of the squares. Vertices of $\Gamma$ have coordinates $(m,k)$, $0\leq m,k \leq n$. Take a subgraph $\Lambda$ of $\Gamma$. So it looks like this:

Let $\Delta$ be the "frame", i.e. the subgraph of $\Gamma$ of points with at least one coordinate equal to $n$, and all the edges between them. Let $A=(x,0)$ , $0 < x < n$, be a point on the lower edge (the entrance) and likewise $\Omega =(y,n)$, $0 < y < n$, a point in the upper edge (the exit).

We say that $\Lambda$ is an $n\times n$ $(A,\Omega)$-labyrinth if it is connected and $A,\Omega\in\Lambda$.

Theseus enters the labyrinth at $A$ and has to reach $\Omega$. He only knows what I said above (except he does not know the value of $n$) and of course ignores the structure of $\Lambda$ and the position of $A$ and $\Omega$ in the lower (respectively upper) edge. At each point (vertex) $v$, just by looking, he has only the following information:

• Whether $v$ is equal to $A$, or to $\Omega$.
• How long are the maximal forward, backward, left and right straight paths $S$ starting from $v$ contained in $\Lambda$. Some lengths may be $0$.
• Whether or not the "end" of $S$ different from $v$ lies in $\Delta$.
• Whether or not the "end" of $S$ different from $v$ is $\Omega$, and whether it's $A$.

Since he enters at $A$, Theseus has a strategy. A strategy is a function that, at each vertex, tells him whether to go forward (resp. bacwards, left or right) by one step depending on the path that has already been walked and on the information gathered so far.

Let $D(\Lambda)$ be the smallest number of steps he must do in order to get to $\Omega$, where the minimum is taken over all the possible strategies.

The question is:

Given $n$, $A$ and $\Omega$, how to construct a labyrinth $\Lambda$ that maximizes $D(\Lambda)$ ?

I'm interested in aswers, if there can be, that do not involve listing all possible strategies and all possible graphs with a "computer".

• This link may be semi-relevant. The basic idea is to generate a maze by generating a random spanning tree. – Tony Huynh Mar 27 '11 at 15:42
• My own question is about making "interesting" labyrinths. – F. C. Sep 19 '17 at 16:42

UPDATE: the answer below works fine for tree-like labyrinths. The previous last paragraph (now struck out) is wrong, though, because the tree-like labyrinth you simulate depends on the random coins you flip.

Suppose the labyrinth is a tree. Further, suppose you do a random depth-first search on a tree, and stop when you reach a specific leaf called Ω. I claim that the expected number of times you traverse each edge is exactly once.

Proof: suppose you're at a node which is an ancestor Ω. There is one subtree of this node that contains Ω, and possibly several other subtrees that don't. For each subtree that doesn't, you explore it with probability ½, and if you do explore it, you traverse every edge twice (this is a property of depth-first-search). There is also one edge leading out of this node that leads to Ω. You will only go down this edge once. QED

Now, for any labyrinth that has a dead-end path, you need never go down the last segment of that path; thus the strategy of depth-first search, and turning back when you see a dead end, takes time strictly less than n2. Thus, there is only one type of tree-like labyrinth that requires maximum expected time to traverse: the type where there are no choices, but just a single path that takes you to from the start to the goal.

If the labyrinth is not tree-like, I believe you can pretend that it is tree-like by pretending there are walls whenever a step will take you back to a section you've already visited, so the expected n2 time upper bound will hold for this kind of labyrinth as well. I don't have a solution.

• The question did not actually ask for expected time to reach $\Omega$, so the literal question as phrased is to maximumize the time taken by the strategy (depending on the labyrinth) that takes you by a shortest path to the goal. The answer is the same: any labyrinth where the graph of connections is a single path. – Bill Thurston Mar 27 '11 at 16:35
• @Peter: I'm confused. Aren't you assuming that Theseus knows the shape of the labyrinth,and is only ignorant of the location of the minotaur? If he's ignorant of both, I don't see what your search algorithm is. – paul Monsky Apr 1 '11 at 15:10
• The search algorithm is depth-first search where the children of a node are traversed in a random order: en.wikipedia.org/wiki/Depth-first_search -- the only possibly unreasonable things I'm assuming is that Theseus will recognize a spot that he has visited before, and that he remembers which way he came (but if I remember my mythology correctly, he solved that problem with string). – Peter Shor Apr 1 '11 at 17:17