wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> fractal maze
        
(Message started by: towr on Oct 23rd, 2003, 6:13am)
Title: fractal maze
Post by towr on Oct 23rd, 2003, 6:13am
from http://www.mathpuzzle.com/

find your way through the maze from - to +,
A,B,C,D,E,F,G,H are smaller versions of the same maze, and if you enter them you have to exit them before you get to the end..
Title: Re: fractal maze
Post by James Fingas on Oct 23rd, 2003, 9:56am
I haven't started on this one, but it's VERY COOL! Big thumbs up  8)
Title: Re: fractal maze
Post by towr on Oct 23rd, 2003, 10:06am
Actually, it seems rather too easy to solve to count as hard  :-/ ..
Despite the claims on mathpuzzle that its hard..
Title: Re: fractal maze
Post by James Fingas on Oct 23rd, 2003, 1:48pm
I guess I must be doing it wrong. It's been plenty hard so far, and it's still not solved...
Title: Re: fractal maze
Post by towr on Oct 23rd, 2003, 2:02pm
Well, if you're doing it by hand it may take a while, but I just programmed a maze-solver in prolog (attached for the interested, one note: I numbered the connections of the maze per side, clockwise)..
Granted it took a while to write out all connections, but the basic algorithm is very simple..
Title: Re: fractal maze
Post by Rezyk on Oct 23rd, 2003, 3:48pm
Here's a list of all the connections (in case it saves someone time/eyestrain).  In labelling the outer connections, I started at the top left and went clockwise from 0 to 31.

0,7,17
1,21,16,G16
2,30,11,F3
3,10,26,B22
4,14,18,A7,C28
5,8,27,A29,E5
6,B2
9,B19
12,15,19,H10
13,20,29,31,C22
22,G18
23,G19
24,G9
25,G26
28,H3
-,A2,C5,E2,E24
+,C16,F1,D16,H16,E23
A13,D7
A17,B30
A27,C8
B11,D9
B21,D1
C12,F0
C19,F20
D0,F8
D17,H12
D21,F13
D29,F10
D31,F7
E9,F29
E17,G4
E20,G0
E25,E27
F24,H6
F31,G25
G1,H15
G14,H26
Title: Re: fractal maze
Post by James Fingas on Oct 24th, 2003, 6:09am
Okay, I found a solution. It didn't go as deep as I was looking before. Here's how NOT to do it (my original method):

Notice that a lot of the pins in the maze are equivalent. Find two pins that are attached together, and, going around to A, B, C, ... H see what wires are connected to those pins. Consolidate the connections to the pins by eliminating all connections to the less used of the two. Now erase that pin from the maze. Continue erasing one pin at a time until you see an easy solution (I erased all but 8 of the pins, and then it was very easy).

The problem with this method is that although it's very simple to use (well, unless you are using paint to erase the wires and change things  :P), when you get to the end and see a solution, you can't figure out how that solution came about. You would have to keep records of every change (maybe saving a version after each pin is eliminated).

Horribly inefficient. Definitely don't do it this way. But if the maze was extremely difficult, and you didn't want to brute-force it, I think this method might be decent.

My second strategy was to just print out 9 copies of the maze, labelling them A, B, C, ... H, and Z (the original). I did a breadth-first fill from the '-' and '+' terminals using a highlighter. It's still not easy to find a solution, until you realize a fundamental fact: on all the submazes, the pins and wires are coloured similarly to the original maze. So after doing a lot of filling and still having no solution, I compared the submazes to the original to see which pins were coloured differently. I quite quickly saw that pin b3 on submaze C was coloured differently, giving me an answer almost immediately.
Title: Re: fractal maze
Post by towr on Oct 25th, 2003, 10:03am

on 10/24/03 at 12:23:08, THUDandBLUNDER wrote:
James, why enjoy solving it when you can just write a program to enjoy solving it for you??
I resent that..
Programming a solver _is_ a way of solving a problem, and enjoyable at that..

If you think you can do it better the old-fashioned way go ahead..
Title: Re: fractal maze
Post by sasto on Mar 22nd, 2009, 9:53pm
What are some stratigies you guys use when solving a Fractal maze. If you could reply that would be great i needs this for a project
Title: Re: fractal maze
Post by towr on Mar 23rd, 2009, 1:58am

on 03/22/09 at 21:53:39, sasto wrote:
What are some stratigies you guys use when solving a Fractal maze. If you could reply that would be great i needs this for a project
I used a breadth first algorithm, keeping track of what 'level' of the maze I was on. Just keep taking all possible steps until you're out, then backtrack to find the path leading there.
Title: Re: fractal maze
Post by Grimbal on Mar 23rd, 2009, 11:01am
If I remember well, I ignored all inner circuits and drew a simplified circuit showing only what pins are connected directly.  That was my level 0 circuit.

Then I replaced each chip with the level 0 circuit and simplified it to show what outer pins are now connected.  That was level 1 circuit.

And so on.  after a few steps, + and - became connected.  I could then reconstruct the whole path.

It doesn't necessarily give the shortest or simplest way, but it minimizes the maximum depth of recursion.
Title: Re: fractal maze
Post by howard roark on Mar 23rd, 2009, 10:26pm
Can the solution ever enter one of those smaller versions of mazes? If yes, isn't that infinite recursion.
Title: Re: fractal maze
Post by towr on Mar 24th, 2009, 1:30am

on 03/23/09 at 22:26:42, howard roark wrote:
Can the solution ever enter one of those smaller versions of mazes?
Moreso, it has to.


Quote:
If yes, isn't that infinite recursion.
Only if you take a wrong turn. Just because you enter a smaller version of the same maze, doesn't mean you're on the same pathway. It's the same as with recursion in programming, you don't get infinite recursion just because you call the same function; the state you enter in recursion has to be different each time (different function arguments from previous calls, or changed global variables).
Title: Re: fractal maze
Post by brac37 on Apr 22nd, 2009, 6:15pm
Do the + and - in the recursive wireframes conduct or not?

The problem whether one can get from + and - is in P. First, you make a graph G1 with all direct connections of the 32 x 9 pins, just what Ryzek did. Next, you make the subgraph G1s of G1 with all connections of the outer 32 pins. After that, you compute G2 by first substituting G1s into G1 and next computing the transitive closure.

The transitive closure of a graph is the graph that shows which vertexes are connected by a path. It can be computed by a triple loop through the vertexes in general with the Floyd–Warshall algorithm, and O(n^3) is polynomial.

Next, you make the subgraph G2s of G2 with all connections of the outer 32 pins.  After that, you compute G3 by first substituting G2s into G1 and next computing the transitive closure. Next, you make the subgraph G3s of G3 with all connections of the outer 32 pins. After that, you compute G4 by first substituting G3s into G1 and next computing the transitive closure, etc.

You stop when the new graph does not differ from the old one. The last graph tells you if + and - are connected.

Another problem is to get an actual solution. For this problem, one can label each edge with the intermediate vertex that the Floyd–Warshall algorithm gives. The subgraphs with only 32 pins do not have labeled vertexes, so no label means either that you have a direct connection or that you must go into recursion.

So one can recursively generate a solution with the labeled edges. A question is whether this is in P. The answer to this question is negative. Here are possible connections (i >= 0):

z[0] -- z[1]
z[2i+2] -- a[2i]
a[2i+1] -- b[2i]
b[2i+1] -- z[2i+3]

One can see that

d(z[2i+2],z[2i+3]) = 2 d(z[2i+2],z[2i+3]) + 3

so the solution can be exponentially long. An interesting paradox.

With only one recursive wireframe instead of two or eight, the solution is polynomial, because when you go from + to -, you can have only polynomially many positions. These positions are parametrized by wireframe position and recursion level, and the recursion level is less than the number of edges.

If you want to compute the distance between + and -, then you just add lengths and take minimal lengths when computing the transitive closure with the Floyd–Warshall algorithm. But it is not clear that the algorithm will remain in P, because the recursion level cannot be estimated by the number of edges.

The pumping lemma for context free grammars solves this problem. The idea of this lemma is the following. You can go into recursion from two pins, but if you go deeper and deeper, then you will go into recursion from two pins from which you already went into recursion. But doing that will of course give a path that is too long. So the recursion level is estimated by 8 x 32 x 32 (even 8 x 16 x 31).
Title: Re: fractal maze
Post by towr on Apr 23rd, 2009, 12:51am

on 04/22/09 at 18:15:16, brac37 wrote:
Do the + and - in the recursive wireframes conduct or not?
It's not mentioned, and it doesn't matter in this case, at least.
Title: Re: fractal maze
Post by towr on Apr 23rd, 2009, 1:15am
I don't see why you wouldn't be able to get a solution in polynomial time though. There is a fixed number of points and therefore a fixed number of connections. If you store (one of) the shortest path for each connection, and get one new connection for each recursion, it still works out to polynomial time.
Title: Re: fractal maze
Post by brac37 on Apr 23rd, 2009, 10:36am

on 04/23/09 at 01:15:53, towr wrote:
I don't see why you wouldn't be able to get a solution in polynomial time though. There is a fixed number of points and therefore a fixed number of connections. If you store (one of) the shortest path for each connection, and get one new connection for each recursion, it still works out to polynomial time.


The solution may be exponential in length, so generating it may take exponentially much time in the input size (but not in the solution size). If you allow some straightforward compression, then you will be able to generate a solution in polynomial time.
Title: Re: fractal maze
Post by mathfridge on May 19th, 2009, 2:29am

on 03/23/09 at 11:01:19, Grimbal wrote:
If I remember well, I ignored all inner circuits and drew a simplified circuit showing only what pins are connected directly.  That was my level 0 circuit.

Then I replaced each chip with the level 0 circuit and simplified it to show what outer pins are now connected.  That was level 1 circuit.

And so on.  after a few steps, + and - became connected.  I could then reconstruct the whole path.

It doesn't necessarily give the shortest or simplest way, but it minimizes the maximum depth of recursion.


This is basically identical to the algorithm I came up with.  Assuming all level n circuits are found before seeking level n+1 circuits this should minimize circuit depth. The initial solution I came up with took 27 steps and had a circuit depth of 3. However this was by hand and I realized there was a shorter solution [hide]whose final path goes through chip F [/hide]at only depth 2. User error :P ;D

This brings up a good question for this type of puzzle. What does an optimal solution look like? Is it depth of recursion or number of times you go in or out of chips? For example I found the following fractal mazes on line.

http://www.mathpuzzle.com/DaedRecursive.gif

The solution I found has a chip depth of 6 and a total of 42 steps in or out of chips. And:

http://www.astrolog.org/labyrnth/maze/fractal2.gif

The solution I found to this on had a chip depth of 7 and a total of 66 steps in or out of chips.

So on this last maze, assuming my work is correct, we know that a 66 steps solution exists. Thus any solution with chip depth 34 or greater must take at least 68 steps but is there a solution with depth between 7 and 33 that has fewer steps? (Also my solution was by hand on each of these. So they might not actually be of smallest depth.)

Thoughts any one? :)

DC
Title: Re: fractal maze
Post by towr on May 19th, 2009, 2:54am

on 05/19/09 at 02:29:21, mathfridge wrote:
This brings up a good question for this type of puzzle. What does an optimal solution look like? Is it depth of recursion or number of times you go in or out of chips?
Personally, I went for the latter. I think that's the easiest one to measure. You might conceivably make a very very long path that only has a shallow recursion depth.


Quote:
http://www.mathpuzzle.com/DaedRecursive.gif
http://www.astrolog.org/labyrnth/maze/fractal2.gif
I'll give these a try later :)
Title: Re: fractal maze
Post by Grimbal on May 29th, 2022, 3:04pm
OK, well, I wrote a program.  Here is the result.
It should be minimal, not necessarily unique.

path: - C5 (5 A29 (29 13) A13 D7 (7 17) D17 H12 (12 15) H15 G1 (1 16) G16 16) C16 +
length: 11

Contacts are numbered clockwise from the top left.
Between the brackets is what happens inside of a circuit.

Anyway, all answers are here: https://www.mathpuzzle.com/fractalmaze.txt


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board