Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

A fractal maze is a maze which contains copies of itself. Eg, the following one by Mark J. P. Wolf from this article:

Begin at the MINUS and make your way to the PLUS. When you enter a smaller copy of the maze, be sure to record the letter name of that copy, as you will have to leave this copy on the way out. You must exit out of each nested copy of the maze that you have entered into, leaving in the reverse order that you entered them in (for example: enter A, enter B, enter C, exit C, exit B, exit A). Think of it as a series of nested boxes. If there is no exit path leaving the nested copy, you have reached a dead end. Color has been added to make the pathways clearer, but it is only decorative. Fractal Maze

If a solution exists, breadth-first-search should find a solution. However, suppose there is no solution to the maze - then our search program would run forever going deeper and deeper.

My question is: given a fractal maze, how can we determine if it has a solution or not?

Or alternatively, for a fractal maze of a given size (number of inputs/outputs per copy), is there a bound on the length of the shortest solution? (if there was such a bound, we could exaustively search only that deep)

share|improve this question
    
After reading the FAQ I do not believe this belongs. It's probably not a reasearch-level theoretical computer science question. Sorry to post in the wrong place. Could someone recommend the proper forum to ask this question and/or move it there? –  Nick Alger Apr 8 '12 at 6:47
    
Mathematics, Computer Science. –  Kaveh Apr 8 '12 at 7:52
    
I considered posting on math.stackexchange since I participate there, but it seemed a little too algorithm-y. I didn't know that there is a computer science stack exchange. If the moderators want to move it to either of those places I wouldn't mind. –  Nick Alger Apr 8 '12 at 8:08
3  
It's not obvious to me that this is off-topic here... obviously off-topic questions usually get more downvotes than upvotes –  Joe Apr 9 '12 at 6:10
7  
Can't you represent any fractal maze as a pushdown automaton, where the stack corresponds to the sequence of submazes that you're in? Then the solubility question would turn into the emptiness problem for context-free languages, which is decidable. –  Peter Shor Apr 9 '12 at 17:22

2 Answers 2

up vote 8 down vote accepted

A quick informal algorithm to prove that the problem is decidable:

  • suppose that there are $n$ Input/Outputs $I_1,...I_n$;
  • build a graph $G$ where each $I_i$, the $MINUS$ and the $PLUS$ are nodes, and replace each nested maze $Mj$ with a $K_n$ subgraph (complete graph); add the edges between $I_i, MINUS, PLUS, Mj_{I_k}$ according to the maze; keep "extern" $Mj_{I_i} \rightarrow Mj_{I_k}$ edges distinct from the corresponding "internal" edges $I_i \rightarrow I_k$ of $Mj$ as a complete subgraph;
  • enumerate all paths from MINUS to PLUS in $G$ (avoiding cycles);
  • if you find a path that doesn't traverse a nested copy, then it is a solution; otherwise expand each "internal" traversals of the nested mazes $Mj$ of each path:

Suppose that a path in the first enumeration is $MINUS \rightarrow A_{I_i} \rightarrow A_{I_j} \rightarrow B_{I_k} \rightarrow B_{I_h} \rightarrow PLUS$, then the path is a valid solution iif there is a path from $I_i \rightarrow I_j$ and from $I_k \rightarrow I_h$ in the original maze (graph $G$).

So we must expand the $A_{I_i} \rightarrow A_{I_j}$ and $B_{I_k} \rightarrow B_{I_h}$ traversals enumerating all the paths from $I_i$ to $I_k$ and from $I_k$ to $I_h$ in $G$.

Infinite loops are detected when we are enumerating all paths from $I_i$ to $I_k$ in an expansion of a path that in a previous stage already contained $... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$ for some submaze $M$ (there are only $n^2$ possible expansions).

A solution is found if we find a path expansion that contains only inputs/outputs $I_i$; the maze has no solution if we cannot further expand the paths without loops.

share|improve this answer
    
Wow! What a clever idea. I think this works but it's still a little fuzzy in my mind, so I'm going to take a bit of time to mull it over before accepting. –  Nick Alger Apr 9 '12 at 14:12
    
Ok yep pretty sure this algorithm is correct. Noting Peter Shor's comment above, I wonder if you could turn this around to provide a proof for the context-free language emptiness decidability problem..? For a given context free language emptiness problem, construct an equivalent fractal maze, then apply this algorithm. –  Nick Alger Apr 10 '12 at 2:52
    
@Nick: A fractal maze corresponds to a reversible pushdown automaton, where if you can make a transition from a state S to a state T, you can also make the transition from T to S. It should be straightforward to show that fractal mazes are in fact equivalent to reversible pushdown automata. There is a theorem saying that (up to polynomial factors) reversible Turing machines have the same power as regular Turing machines. I don't know if anybody has looked into reversible pushdown automata before, so I don't know whether anything is known about them. –  Peter Shor Apr 10 '12 at 14:29
    
@Peter: I found this Reversible Pushdown Automata, but the definition of "reversible" seems different. (P.S. congratulations for the simple and clean interpretation of a fractal maze as a PDA!!!) –  Marzio De Biasi Apr 10 '12 at 15:54
1  
The above algorithm could be extended to directed graphs (irreversibe fractal mazes), you would just have $2n^2$ possible expansions to consider ($I_k \rightarrow I_j$ and $I_j \rightarrow I_k$). –  Nick Alger Apr 10 '12 at 17:02

This is not an "answer" to my question, but rather an extended comment that people here might find interesting.

I claim that there is a natural "analysis-type" definition of a maze and a solution, and it differs from the computer-science/graph-theoretic definition we've used here. In particular, you can have a fractal maze that has a "solution" under the analysis definition, but would be declared unsolvable by Marizio De Biasi's algorithm and Peter Shor's pushdown automata technique.

Definition: A maze $M$ is a compact subset of the plane $M \subset \mathbb{R}^2$ containing a start point and an endpoint $s,e \in M$, respectively. A solution is a continuous function $f:[0,T] \rightarrow M$ such that $f(0)=s$ and $f(T)=e$.

Now consider the the Hilbert Curve:

Hilbert curve gif from wikipedia

One could interpret this curve as a "fractal maze" with the following diagram: enter image description here

Since the Hilbert Curve iterations converge uniformly, that uniform limit is a continuous path that solves the maze in the analytic sense. It's as if you were able to do the following recursively defined infinite set of moves $P$:

$P = APA^{-1}BPB^{-1}CPC^{-1}DPD^{-1}$

Now you might argue that this is not in the spirit of fractal mazes since the Hilbert curve fills the entire square and therefore you could just draw a straight line segment from the start to the finish. This objection is easily overridden though - simply use the hilbert curve diagram embedding directly, as shown here:

enter image description here

This too contains a sequence of uniformly convergent continuous paths going from the start to the finish, by the same argument used to show the uniform convergence of the Hilbert curve. However it is a true "fractal maze" in the sense that it does not fill the whole space.

Thus we have a fractal maze that is solvable by the analytic definition, but unsolvable by the graph theoretic definition..!?

Anyways, I'm pretty sure my logic is correct, but it seems counterintuitive so if anyone can shed some light on this I would appreciate it.

share|improve this answer
    
A naive comment: the "submazes" of the Hilbert curve are smaller, so in the "continuous world" it works; in the "discrete world" you'll never make an "exit" move because you continue to enter the first submaze (like an endless zoom on the bottom-left of the Hilbert curve). It resembles the Zeno's paradoxes –  Marzio De Biasi May 9 '12 at 11:03
2  
P.S. I think that there is no need of a fractal curve: a simple horizontal line from s to f with a single central submaze (which has a single horizontal line with a sub-submaze ecc. ecc.) leads to the same considerations. –  Marzio De Biasi May 9 '12 at 11:10
    
Good point. If you do that with a sub-box of width 1/2 placed on the far right, it's not just like zeno's paradox, you get exactly zenos paradox. After further consideration it looks like the continuous definition isn't well suited for fractal mazes since it makes almost every fractal maze solvable. –  Nick Alger May 9 '12 at 18:23
    
but it is well suited for Zen labyrinth meditation (Google around for the difference between a labyrinth and maze in a meditation context) :-) –  Marzio De Biasi May 9 '12 at 21:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.