How to construct a maximally difficult NxN labyrinth ?

Question

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:

alt text http://www.ich-liebt-du.de/wp-content/uploads/2008/09/labyrinth.jpg

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".

Answer 1

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 n². 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 n² time upper bound will hold for this kind of labyrinth as well. I don't have a solution.