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