Author |
Topic: fractal maze (Read 12925 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
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 23rd, 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 23rd, 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: 13730
|
|
Re: fractal maze
« Reply #2 on: Oct 23rd, 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 23rd, 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: 13730
|
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..
|
| « Last Edit: Oct 23rd, 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 23rd, 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,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
|
| « Last Edit: May 29th, 2022, 3:08pm by Grimbal » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: fractal maze
« Reply #6 on: Oct 24th, 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 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.
|
|
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: 13730
|
|
Re: fractal maze
« Reply #7 on: Oct 25th, 2003, 10:03am » |
Quote Modify
|
on Oct 24th, 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 old-fashioned way go ahead..
|
| « Last Edit: Oct 25th, 2003, 10:05am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sasto
Newbie
Posts: 2
|
|
Re: fractal maze
« Reply #8 on: Mar 22nd, 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: 13730
|
|
Re: fractal maze
« Reply #9 on: Mar 23rd, 2009, 1:58am » |
Quote Modify
|
on Mar 22nd, 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: 7527
|
|
Re: fractal maze
« Reply #10 on: Mar 23rd, 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 23rd, 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: 13730
|
|
Re: fractal maze
« Reply #12 on: Mar 24th, 2009, 1:30am » |
Quote Modify
|
on Mar 23rd, 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 22nd, 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 22nd, 2009, 7:27pm by brac37 » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: fractal maze
« Reply #14 on: Apr 23rd, 2009, 12:51am » |
Quote Modify
|
on Apr 22nd, 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: 13730
|
|
Re: fractal maze
« Reply #15 on: Apr 23rd, 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 23rd, 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 23rd, 2009, 10:36am » |
Quote Modify
|
on Apr 23rd, 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 19th, 2009, 2:29am » |
Quote Modify
|
on Mar 23rd, 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 19th, 2009, 2:52am by mathfridge » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: fractal maze
« Reply #18 on: May 19th, 2009, 2:54am » |
Quote Modify
|
on May 19th, 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
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: fractal maze
« Reply #19 on: May 29th, 2022, 3:04pm » |
Quote Modify
|
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
|
| « Last Edit: May 29th, 2022, 3:14pm by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
fractal_maze.prolog.doc