Hello again! I noticed Mark Wolf's new fractal Maze. Although it's smaller
than the first one, it has a solution that goes twice as deep. Below is a
solution of depth four. Let's label the 16 pins around the outside as
follows: Pins 03 go from left to right across the top, pins 47 go from top
to bottom down the left side, pins 811 go from left to right across the
bottom, and pins 1215 go from top to bottom down the right side.
0 1 2 3
4 12
5 A B 13
6 / C 14
7 15
8 9 10 11
From  enter A8 Stack:
From 8 leave 2 Stack: A
From A2 enter C13 Stack:
From 13 enter B15 Stack: C
From 15 enter A9 Stack: CB
From 9 enter A6 Stack: CBA
From 6 leave 9 Stack: CBAA
From A9 leave 10 Stack: CBA
From A10 enter A4 Stack: CB
From 4 leave 0 Stack: CBA
From A0 leave 4 Stack: CB
From B4 enter A15 Stack: C
From 15 enter A9 Stack: CA
From 9 leave 6 Stack: CAA
From A6 leave 9 Stack: CA
From A9 leave 10 Stack: C
From C10 goto + Stack:
Not all traditional Mazes can be solved with the lefthand or righthand
rule. Wall following will fail to find a solution for Mazes where the start
and goal are on separate islands of walls, because your path will take you
in a loop around the starting island and you'll find yourself back at the
start. To guarantee a solution through a traditional Maze when walking
through it, use Tremaux's Algorithm or something similar to mark your path,
to keep from going in circles and to ensure you try all paths. Wall
following (and Tremaux's Algorithm for that matter) will probably fail to
find the solution to a recursive fractal Maze, since the Maze is effectively
infinite size, meaning you can go down a false path forever.
What you can do in a fractal Maze (or any other Maze for that matter) is
define a distance threshold beyond which you won't go. That distance can be
defined in terms of depth (e.g. don't enter a chip beyond depth 2) or in
terms of junctions (e.g. don't follow more than 2 junctions from the start).
Then do Tremaux's algorithm or whatever to try to find a solution. If that
fails to find any solution, increase the distance by one, and try again.
Eventually you'll find a solution, which will be a shortest solution in
terms of nesting/junction distance. This is basically a person inside a
Maze implementing a breadth first search, or rather a depth first search
with cutoff (which is a simple way of implementing a breadth first search).
O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O
* Walter D. "Cruiser1" Pullen :) ! *
O Follow the "Path" in life's Maze: http://www.astrolog.org/labyrnth.htm O
*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*O*

Wow, this was tougher than the bigger maze. The first solution I found went
three levels deep, and I don't know if it's the shortest or the shallowest,
but I don't intend to look for any more! :)
In this notation, the North and South exits are labelled 14 from left to
right, and the West and East exits are labelled 14 from top to bottom.
Parentheses are used to indicate a submaze, and I put the letter of the
submaze both before AND after the parentheses, so I wouldn't get lost.
[]

A(S1A(E1B(N4B(N1W1)BA(E4S3)AA(W1N1)AW1)BA(E4S3)AA(W1N1)AW1)AA(S3A(S2W3)AS2)AE4)A
 B(W1A(N1W1)AA(S3A(S2W3)AW3)AW3)B
 C(W2A(N1W1)AA(S3A(S2W3)AS2)AS3)C
 [+]
I have no idea what algorithm could be used by someone INSIDE the maze. It
may depend on whether or not there is some indicator when the person is
entering or exiting a submaze; would there be a door, or would the corridor
just continue? And I guess any marks left on a corridor won't appear in the
submazes. The person in the maze might just have to resort to making a map.
But what if the person doesn't know it's a fractal maze? Could he eventually
figure it out by mapping it? The more I think about this, it seems there's a
potential sequel to the movie "Cube" here...
Eric







