Author 
Topic: fractal maze (Read 10218 times) 

towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13614

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

« Last Edit: Oct 23^{rd}, 2003, 6:14am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: fractal maze
« Reply #1 on: Oct 23^{rd}, 2003, 9:56am » 
Quote Modify

I haven't started on this one, but it's VERY COOL! Big thumbs up


IP Logged 
Doc, I'm addicted to advice! What should I do?



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13614


Re: fractal maze
« Reply #2 on: Oct 23^{rd}, 2003, 10:06am » 
Quote Modify

Actually, it seems rather too easy to solve to count as hard .. Despite the claims on mathpuzzle that its hard..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: fractal maze
« Reply #3 on: Oct 23^{rd}, 2003, 1:48pm » 
Quote Modify

I guess I must be doing it wrong. It's been plenty hard so far, and it's still not solved...


IP Logged 
Doc, I'm addicted to advice! What should I do?



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13614

Well, if you're doing it by hand it may take a while, but I just programmed a mazesolver 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..

« Last Edit: Oct 23^{rd}, 2003, 2:04pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Rezyk
Junior Member
Gender:
Posts: 85


Re: fractal maze
« Reply #5 on: Oct 23^{rd}, 2003, 3:48pm » 
Quote Modify

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,G18 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

« Last Edit: Oct 24^{th}, 2003, 12:47pm by Rezyk » 
IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: fractal maze
« Reply #6 on: Oct 24^{th}, 2003, 6:09am » 
Quote Modify

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 ), 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 bruteforce 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 breadthfirst 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.


IP Logged 
Doc, I'm addicted to advice! What should I do?



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13614


Re: fractal maze
« Reply #7 on: Oct 25^{th}, 2003, 10:03am » 
Quote Modify

on Oct 24^{th}, 2003, 12:23pm, 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 oldfashioned way go ahead..

« Last Edit: Oct 25^{th}, 2003, 10:05am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



sasto
Newbie
Posts: 2


Re: fractal maze
« Reply #8 on: Mar 22^{nd}, 2009, 9:53pm » 
Quote Modify

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


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13614


Re: fractal maze
« Reply #9 on: Mar 23^{rd}, 2009, 1:58am » 
Quote Modify

on Mar 22^{nd}, 2009, 9:53pm, 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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7393


Re: fractal maze
« Reply #10 on: Mar 23^{rd}, 2009, 11:01am » 
Quote Modify

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.


IP Logged 



howard roark
Full Member
Posts: 241


Re: fractal maze
« Reply #11 on: Mar 23^{rd}, 2009, 10:26pm » 
Quote Modify

Can the solution ever enter one of those smaller versions of mazes? If yes, isn't that infinite recursion.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13614


Re: fractal maze
« Reply #12 on: Mar 24^{th}, 2009, 1:30am » 
Quote Modify

on Mar 23^{rd}, 2009, 10:26pm, 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).


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



brac37
Newbie
Gender:
Posts: 23


Re: fractal maze
« Reply #13 on: Apr 22^{nd}, 2009, 6:15pm » 
Quote Modify

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

« Last Edit: Apr 22^{nd}, 2009, 7:27pm by brac37 » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13614


Re: fractal maze
« Reply #14 on: Apr 23^{rd}, 2009, 12:51am » 
Quote Modify

on Apr 22^{nd}, 2009, 6:15pm, 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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13614


Re: fractal maze
« Reply #15 on: Apr 23^{rd}, 2009, 1:15am » 
Quote Modify

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.

« Last Edit: Apr 23^{rd}, 2009, 1:16am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



brac37
Newbie
Gender:
Posts: 23


Re: fractal maze
« Reply #16 on: Apr 23^{rd}, 2009, 10:36am » 
Quote Modify

on Apr 23^{rd}, 2009, 1:15am, 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.


IP Logged 



mathfridge
Newbie
Gender:
Posts: 1


Re: fractal maze
« Reply #17 on: May 19^{th}, 2009, 2:29am » 
Quote Modify

on Mar 23^{rd}, 2009, 11:01am, 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 whose final path goes through chip F at only depth 2. User error 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

« Last Edit: May 19^{th}, 2009, 2:52am by mathfridge » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13614


Re: fractal maze
« Reply #18 on: May 19^{th}, 2009, 2:54am » 
Quote Modify

on May 19^{th}, 2009, 2:29am, 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:I'll give these a try later


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



