|Main||Links||Orders||Post||Next Page||Next + 10|
A COMPLEX MAZE
(a+bi) + (c+di) = (a+c) + i(b+d)
(a+bi) - (c+di) = (a-c) - i(b-d)
(a+bi)(c+di) = (ac-bd) + i(bc+ad)
(a+bi)/(c+di) = ( (ac+bd) + i(bc-ad) )/(c2+d2)
The book Visual Complex Analysis by Tristan Needham starts with this quote: "The present book openly challenges the current dominance of purely symbolic logical reasoning by using new, visually accessible arguments to explain the truths of elementary complex analysis." I heartily agree with this philosophy, and highly recommend the book.
I found these calculations tedious so I wrote a program to solve your maze. It exhausted the search space (pruning paths that lead to the same cell with the same running total -- there were *lots* of these) and found these solutions:
4+i - 3-2i / 1+i + 2+5i / 1+i - 10 + 7-3i + 2+3i = 1-i
4+i - 3-2i / 1+i - 7-3i + 10 - 1+i + 7-3i / 2+3i = 1-2i
4+i * 1+3i / 4+i - 2+5i - 1+3i + 1+i * 7-3i + 2+3i = 1+20i
4+i * 1+3i / 4+i - 2+5i - 1+3i + 10 - 7-3i + 2+3i = 3-i
4+i * 1+3i / 4+i - 2+5i - 1+3i + 10 - 7-3i - 2+3i = -1+7i
4+i * 1+3i / 4+i - 2+5i - 1+i + 10 - 7-3i + 2+3i = 3+i
4+i * 1+3i / 4+i - 2+5i - 1+i + 10 - 7-3i * 2+3i = 8-i
4+i * 1+3i / 4+i - 2+5i - 1+i + 10 - 7-3i - 2+3i = -1+5i
4+i * 1+3i - 2+5i / 3-2i + 1+i - 3-5i - 7-3i / 2+3i = -1+2i
4+i * 1+3i - 2+5i / 3-2i + 1+i - 10 + 7-3i + 2+3i = 1+i
4+i * 1+3i / 4+i + 3-2i - 3-5i + 2+5i / 1+i * 7-3i - 2+3i = -1+20i
4+i - 3-2i / 1+i + 2+5i / 1+i + 10 / 2+5i * 1+3i + 10 / 7-3i * 2+3i = 1+8i
I saw your complex maze and I wrote a little program to find the solutions. I didn't spend much time checking it,but it should be right. The number before the solution is the path length. The attachment is the analysis with the max depth of 18. [And he sent 3129 solutions]
* False paths average length: 16.575655
* False paths: 1771440
* Max depth (18) reached 1300875 times
* Total solutions found : 3129
I have had a lot of fun with your complex maze. I found my first solution (which turns out to be the shortest one) by hand while working on the state diagram for the maze. I decided that the problem of elucidating the state diagram was more suitable for a computer than for me, so I wrote a program to do it. It found a total of 235 accessable states (each characterized by a position in the maze and a particular running total), and 411 allowed transitions between pairs of states.
When I extended my program to actually trace through the state diagram to find solutions, I found (as expected) that there are cycles and multiple solutions. In fact, there are many, many, many cycles, and many, many cycle-less solutions. (And infinately many solutions that do contain cycles.) There are 16 distinct final states possible for paths through the maze; the shortest paths leading to each are below. I suspect that generating a nontrivial maze of this kind that has only one solution is a very difficult problem.
The 16 possible final totals are 1+i, 3+i, -1-5i, 8-i, 1-2i, 1-i, 1+20i, 1+8i, -1+2i, -1-20i, -1+i, -1-i, -1-8i, 1+5i, -3-i, -8+i
J B Gill:
I was intrigued with your Complex Maze puzzle, so I thought I'd give it a whirl. After finding a few solutions, I discovered that there are probably dozens of ways to solve this, most of which involve a handful of common "states" (I define a "state" as being on a specific square with a specific running total). I also read your comments on a "state diagram" for this puzzle and I was curious as to how many possible states there are for this maze, so I wrote a simple program that helped me figure it out. I attached the output and source code in case you're interested. The way I determined how many unique states there are is count the number of lines in the output, then count the number of lines that say "been in this state", multiply it by 2, and subtract from the total lines.
From this I determined that there are 237 unique states for this puzzle
(unless I miscounted). This output also shows that there are solutions
of at least 63 steps which don't re-use a state - there may be longer ones.
(I didn't keep track of unique states per solution, just unique states
overall.) There are also 16 unique solution states.
The output can also be used to list all possible solutions to the puzzle (if you know how to read it correctly). [He also sent a Java Program and output.
The shortest solution takes five steps
(4+i) - (3-2i)
=> (1+3i) / (1+i)
=> (2+i) - 10
=> (-8+i) + (7-3i)
=> (-1-2i) + (2+3i)
There are some loops in the maze, so there are infinitely many paths in all. There's a loop of length 9 that is accessible from the start and which can be extended after any number of cycles to reach the finish:
Here are the values that you can have when you reach the finish (I think this is exhaustive, but I don't have a proof -- the state diagram is huge):
-8+i -3-i -1-20i -1-8i -1-5i -1-i -1+i -1+2i
1-i 1-2i 1+i 1+5i 1+8i 1+20i 3+i 8-i
[Gareth also sent me some Emacs LISP code.]