Pullen's Fractal Maze

Hello! On mathpuzzle.com, in "Material added 13 May 05", you have an item
for "Walter D. Pullen's Fractal Maze Generator", where you have a special
10x4 pin 7 chip Maze, and ask "Can anyone solve the following maze". It
doesn't look like anybody has submitted an answer yet, so I will solve a
Maze created by my own program. ;) It turns there's one unique shortest
solution, and it's of length 43, and requires entering a depth of 7 (this
verified by computer). That's a complicated Maze, with a long and deep
solution, a very good choice! :)

Below is the solution. Let's label the 40 pins around the outsides as
follows: Indicate the edge by its direction (NWSE) followed by a number
ranging from 1-10 left to right, or 1-4 top to bottom. The chips are
numbered 1-7, so e.g. "1S10" means the rightmost bottom pin on chip #1,
and "W1" means the topmost left pin on the outer rim. Notice how the
solution has two instances of a long subsequence of stack 65515, but
going in opposite directions, i.e. the way to cross chip #6 between 6E4
and 6S7. (Add a link between E4 and S7 on the outer rim and the solution
becomes much shorter!) Anyway:

From ---- Enter 5E4  - Stack:
From E4   Enter 4S10 - Stack: 5
From S10  Leave E2   - Stack: 54
From 4E2  Enter 1E3  - Stack: 5
From E3   Leave E1   - Stack: 51
From 1E1  Enter 2W3  - Stack: 5
From W3   Enter 6E4  - Stack: 52
From E4   Enter 5E1  - Stack: 526
From E1   Enter 5S9  - Stack: 5265
From S9   Enter 4S10 - Stack: 52655
From S10  Leave E2   - Stack: 526554
From 4E2  Enter 1E3  - Stack: 52655
From E3   Leave E1   - Stack: 526551
From 1E1  Enter 1E2  - Stack: 52655
From E2   Enter 5S3  - Stack: 526551
From S3   Leave N2   - Stack: 5265515
From 5N2  Leave N5   - Stack: 526551
From 1N5  Leave S3   - Stack: 52655
From 5S3  Leave S10  - Stack: 5265
From 5S10 Leave S7   - Stack: 526
From 6S7  Enter 5N2  - Stack: 52
From N2   Leave S3   - Stack: 525
From 5S3  Leave E2   - Stack: 52
From 2E2  Leave W1   - Stack: 5
From 5W1  Enter 5S10 - Stack:
From S10  Enter 5S3  - Stack: 5
From S3   Leave N2   - Stack: 55
From 5N2  Enter 6S7  - Stack: 5
From S7   Enter 5S10 - Stack: 56
From S10  Enter 5S3  - Stack: 565 
From S3   Enter 1N5  - Stack: 5655
From N5   Enter 5N2  - Stack: 56551
From N2   Leave S3   - Stack: 565515
From 5S3  Leave E2   - Stack: 56551
From 1E2  Enter 1E1  - Stack: 5655
From E1   Leave E3   - Stack: 56551
From 1E3  Enter 4E2  - Stack: 5655
From E2   Leave S10  - Stack: 56554
From 4S10 Leave S9   - Stack: 5655
From 5S9  Leave E1   - Stack: 565
From 5E1  Leave E4   - Stack: 56
From 6E4  Leave W3   - Stack: 5
From 5W3  Goto  ++++

Walter D. Pullen 

-----------------------------------------------------
I have to admit, these things are addictive.

I found a solution only (?) 6 levels deep.

The north and south exits are numbered 1 to 10 from left to right. The west 
and east exits are numbered 1 to 4 from top to bottom. Parentheses represent 
sub-mazes. The sub-mazes are labeled both before and after the parentheses, 
to keep me from getting lost.

Let point A be the intersection just northwest of the northwest corner of 
sub-maze 1.
Let point B be the intersection just north of gate S9.
A path from A to B is:

A - 1(N5-5(N2-S3)5-E2)1 - 1(E1-E3)1 - 4(E2-S10)4 - B

This path, and its reverse (from B to A), appear several times in this 
solution to the maze.
For brevity, it will be written as "A-B" or "B-A".

[-]

- 2(S3- 1(N5- 5(N2- A-B -S9)5 - 2(E1-5(S9- BB-A -S3)5-E2)2 -W1)1 -W4)2

- 2(E2- 5(S3-N2)5 - 6(S7- 5(S10- 5(S3- A-B --S9)5 -E1)5 -E4)6 -W3)2

- 1(E1-E3)1 - 4(E2-S10)4

- 5(E1- 5(S9- B-A -N2)5 - 6(S7- 5(S10- 5(S3-- A-B -S9)5 -E1)5 -E4)6 -W3)5

- [+]


--Eric von Laudermann
----------------------------------------------------------
Hi Ed!

I'm glad to see the fractal maze making a return on MathPuzzle. If you
recall, I wrote a Javascript simulator for the maze and submitted
color-coded solutions. This last puzzle is quite big so I will just
submit the solution in my simulator's notation:

The solution is a list of nodes. A node is either a -, +, or a pin
designated as [chiplabel][side][pin#]. The chips labeled 1-7 are the
internal chip; chip X is the big chip. Sides are N/E/S/W for
north/east/south/west respectively. Pins are numbered 1..10 from
left-to-right or top-to-bottom.

These solution enters only 5/6 at the top most level respectively.
There are others, possible shorter solutions.

Solution#1:
Outline: 5(5(2(5(411(5))6(5(5(1(5)14))))1(5(411(5))))6(5(5(1(5)14)))))
-|
5E4 => XE4|5
5E1 => XE1|55
2E1 => XE1|255
5S9 => XS9|5255
4S10 => XS10|45255
XE2 => 4E2|5255
1E3 => XE3|15255
XE1 => 1E1|5255
1E2 => XE2|15255
5S3 => XS3|515255
XN2 => 5N2|15255
XN5 => 1N5|5255
XN2 => 5N2|255
6S7 => XS7|6255
5S10 => XS10|56255
5S3 => XS3|556255
1N5 => XN5|1556255
5N2 => XN2|51556255
XS3 => 5S3|1556255
XE2 => 1E2|556255
1E1 => XE1|1556255
XE3 => 1E3|556255
4E2 => XE2|4556255
XS10 => 4S10|556255
XS9 => 5S9|56255
XE1 => 5E1|6255
XE4 => 6E4|255
XW3 => 2W3|55
1E1 => XE1|155
5S9 => XS9|5155
4S10 => XS10|45155
XE2 => 4E2|5155
1E3 => XE3|15155
XE1 => 1E1|5155
1E2 => XE2|15155
5S3 => XS3|515155
XN2 => 5N2|15155
XN5 => 1N5|5155
XN2 => 5N2|155
XN5 => 1N5|55
XN2 => 5N2|5
6S7 => XS7|65
5S10 => XS10|565
5S3 => XS3|5565
1N5 => XN5|15565
5N2 => XN2|515565
XS3 => 5S3|15565
XE2 => 1E2|5565
1E1 => XE1|15565
XE3 => 1E3|5565
4E2 => XE2|45565
XS10 => 4S10|5565
XS9 => 5S9|565
XE1 => 5E1|65
XE4 => 6E4|5
XW3 => 5W3|
+|

Solution #2:
Outline: 
6(3(2(1(2(5(1(5)14)))4(5(1(5)14)2(5(411(5))))3(5(5(411(5)))))7(41(5(411(5)))7(5(5(1(5)14)))))))
-|
6S1 => XS1|6
3W1 => XW1|36
2W4 => XW4|236
1W1 => XW1|1236
2E2 => XE2|21236
5S3 => XS3|521236
1N5 => XN5|1521236
5N2 => XN2|51521236
XS3 => 5S3|1521236
XE2 => 1E2|521236
1E1 => XE1|1521236
XE3 => 1E3|521236
4E2 => XE2|4521236
XS10 => 4S10|521236
XS9 => 5S9|21236
XE1 => 2E1|1236
XE3 => 1E3|236
4E2 => XE2|4236
5S3 => XS3|54236
1N5 => XN5|154236
5N2 => XN2|5154236
XS3 => 5S3|154236
XE2 => 1E2|54236
1E1 => XE1|154236
XE3 => 1E3|54236
4E2 => XE2|454236
XS10 => 4S10|54236
XS9 => 5S9|4236
2E1 => XE1|24236
5S9 => XS9|524236
4S10 => XS10|4524236
XE2 => 4E2|524236
1E3 => XE3|1524236
XE1 => 1E1|524236
1E2 => XE2|1524236
5S3 => XS3|51524236
XN2 => 5N2|1524236
XN5 => 1N5|524236
XS3 => 5S3|24236
XE2 => 2E2|4236
XW1 => 4W1|236
3E4 => XE4|3236
5E1 => XE1|53236
5S9 => XS9|553236
4S10 => XS10|4553236
XE2 => 4E2|553236
1E3 => XE3|1553236
XE1 => 1E1|553236
1E2 => XE2|1553236
5S3 => XS3|51553236
XN2 => 5N2|1553236
XN5 => 1N5|553236
XS3 => 5S3|53236
XS10 => 5S10|3236
XN4 => 3N4|236
XN6 => 2N6|36
7E4 => XE4|736
4S10 => XS10|4736
XE2 => 4E2|736
1E3 => XE3|1736
5S9 => XS9|51736
4S10 => XS10|451736
XE2 => 4E2|51736
1E3 => XE3|151736
XE1 => 1E1|51736
1E2 => XE2|151736
5S3 => XS3|5151736
XN2 => 5N2|151736
XN5 => 1N5|51736
XN2 => 5N2|1736
XN5 => 1N5|736
7N3 => XN3|7736
5E2 => XE2|57736
5S3 => XS3|557736
1N5 => XN5|1557736
5N2 => XN2|51557736
XS3 => 5S3|1557736
XE2 => 1E2|557736
1E1 => XE1|1557736
XE3 => 1E3|557736
4E2 => XE2|4557736
XS10 => 4S10|557736
XS9 => 5S9|57736
XE1 => 5E1|7736
XE4 => 7E4|736
XN8 => 7N8|36
XS6 => 3S6|6
XN10 => 6N10|
+|

Regards,
Yogy Namara
------------------------------------------------------------
Here is a solution to the fractal maze, that may not be minimal.

First, notation.
I labeled the pins this way:
The top (North) pins from left to right: N0 ... N9
The bottom (South) pins from left to right: S0 ... S9
The left (West) pins from top to bottom: W0 ... W3
The right (East) pins from top to bottom: E0 ... E3

There are a number of equivalence classes of pins.
These are pins that are joined together within the maze,
without having to go up or down a level in the maze.
These are:
(A)   N1 == s2
(B)   N3 == S6
(C)   E0 == E2
(D)   E1 == S9
(E)   E3 == S8
Let's call these axioms.  They are obvious.

I solved the maze by building more equivalence classes that
usually depend on going only deeper into the maze, with a few
exceptions.

Notation:
  B:Px - Inside box B at pin Px.
  ABC:Px - Several levels down the maze, the deepest being C at pin Px.

I start with the simplest, and build up.

Theorem 1: E1 == N4.
  Start at E1.
  Go down into 5 at S2.
  Use Axiom A to get to N1.
  Go up out of 5 to N4.
  QED

The next theorem goes above the starting level,
so it depends on the box as well as the pin.

Theorem 2: 1:E0 == 4:E1
  Start at 1:E0.
  Use Axiom C to get to 1:E2.
  Go up out of 1, and into 4:E1.
  QED

Theorem 2.1: 1:E0 == 4:S9
  Start at 1:E0.
  Use Theorem 2 to get to 4:E1.
  Use Axiom D to get to 4:S9.
  QED

Theorem 3: 1:N4 == 4:S9
  Start at 1:N4.
  Use Theorem 1 to get to 1:E1.
  Go out of 1, and into 1:E0.
  Use Theorem 2.1 to get to 4:S9.
  QED

Theorem 4: S2 == S8
  Start at S2.
  Go down into 1:N4.
  Go to 4:S9.   (3)
  Go up to S8.
  QED

Theorem 4.1: S2 == E3
  Start at S2.
  Go to S8.  (4)
  Go to E3.  (E)
  QED

Theorem 5: E2 == W0
  Start at E2.
  Go down to 2:E0.
  Go down to 25:S8.
  Go to 25:S2.  (4)
  Go up to 2:E1.
  Go up to W0.
  QED

Theorem 6: S6 == S8
  Start at S6.
  Go down to 5:S9.
  Go down to 55:S2.
  Go to 55:S8.  (4)
  Go up to 5:E0.
  Go up to S8.
  QED

Theorem 6.1: S6 == E3
  Start at S6.
  Go to S8.  (6)
  Go to E3.  (E)
  QED

Theorem 7: N4 == E2
  Start at N4.
  Go down to 5:N1.
  Go down to 51:N4.
  Go to 54:S9.  (3)
  Go up to 5:S8.
  Go up to E2.
  QED

Theorem 7.1: N4 == E0
  Start at N4.
  Go to E2.  (7)
  Go to E0.  (C)
  QED


Now that these little transfomations have been found,
we can solve the maze.

Theorem 8: + == -
  Start at +.
  Go to 1:S1.
  Go down to 16:W3.
  Go down to 161:W0.
  Go to 161:E2.  (5)
  Go up and down to 164:E1.
  Go to 164:S9.  (D)
  Go up to 16:S8.
  Go to 16:S6.  (6)
  Go up to 1:N4.
  Go to 1:E1.  (1)
  Go up and down to 2:W2.
  Go down to 26:E3.
  Go down to 264:S9.
  Go to 261:E0.  (2.1)
  Go up and down to 262:W2.
  Go down to 2626:E3.
  Go to 2626:S6.  (6.1)
  Go up to 262:N4.
  Go to 262:E0.  (7.1)
  Go up to 26:E2.
  Go to 26:N4.  (7)
  Go up and down to 23:S2.
  Go to 23:E3.  (4.1)
  Go up and down to 24:W0.
  Go to 24:E2.  (5)
  Go down to 245:S8.
  Go to 245:S2.  (4)
  Go up to 24:E1.
  Go to 21:E0.  (2)
  Go up and down to 21:E1.
  Go to 21:N4.  (1)
  Go up to 2:S2.
  Go up and down to -.
  QED


Rolan Christofferson

----------------------------------------------------------
I've solved your newest fractal maze; my solution is below.  This is a 
solution of minimal depth (I think), and among all such solutions its 
length is minimal (ditto). 

I've had an idea for a fractal maze variant, but not managed to 
implement it: the Tumbolian fractal maze (after Goedel, Escher, Bach).  
Somewhere within the maze would be a Tumbolia node, and entering it 
would manipulate the stack of nodes entered so far.  For instance, the 
Tumbolia node might perform a swap on the stack, so if you enter A, 
enter B, enter C, and touch this node, you'd have to exit B, exit C, and 
exit A to finish.  Such a maze wouldn't be susceptible to the bottom-up 
approach I use to solve standard fractal mazes. 
Perhaps some mathpuzzler out there can make something of this?

Alex Fink

Number the pins clockwise, with 1 at the upper left. 

-
5.14
5.16
2.11
2.5.16
2.5.4.15
2.5.4.12
2.5.1.13
2.5.1.11
2.5.1.12
2.5.1.5.22
2.5.1.5.2
2.5.1.5
2.5.2
2.6.18
2.6.5.15
2.6.5.5.22
2.6.5.5.1.5
2.6.5.5.1.5.2
2.6.5.5.1.5.22
2.6.5.5.1.12
2.6.5.5.1.11
2.6.5.5.1.13
2.6.5.5.4.12
2.6.5.5.4.15
2.6.5.5.16
2.6.5.11
2.6.14
2.26
1.11
1.13
4.12
4.15
5.11
5.5.16
5.5.4.15
5.5.4.12
5.5.1.13
5.5.1.11
5.5.1.12
5.5.1.5.22
5.5.1.5.2
5.5.1.5
5.5.2
5.6.18
5.6.5.15
5.6.5.5.22
5.6.5.5.1.5
5.6.5.5.1.5.2
5.6.5.5.1.5.22
5.6.5.5.1.12
5.6.5.5.1.11
5.6.5.5.1.13
5.6.5.5.4.12
5.6.5.5.4.15
5.6.5.5.16
5.6.5.11
5.6.14
5.26
+
Alex Fink