Re: DIS: The Maze Craze
From Bernie Cosell <ber...@fantasyfarm.com>
· alt.ascii-art
· 4 Mar 1994 20:24 · View full thread
· report
In article <Nve...@emr1.emr.ca>, Normand Veilleux writes:
} One thing that has always amazed me about mazes is that a lot of
} people believe that they are always easier if you start from FINISH
} and move towards START. I have never seen any facts or arguments
} proving or disproving this belief. So, is this fact or fiction?
Largely a fiction I'd say. One key problem you'll have in trying
to pursue this [especially by using examples, rather than
analysis/proofs] is that you'll need a *definition* of "difficult".
The matter of the difficulty of a maze is [as far as I can tell]
a VERY subtle matter and has to do a lot with what the 'rules' for
the maze are and what particular heuristics a person uses.
} ... If this argument holds mathematically (are there mathematicians in
} the crowd?) then the belief is proven to be impossible to achieve
} in all possible cases which makes it erroneous.
Well, it cannot "hold mathematically" until you have a
mathematically precise definition of "difficulty". Is a mirror
image of a maze the SAME difficulty as the original? Perhaps not
if you are a fan of the 'right hand rule' --- one might be trivial
and the other tortuous, even though they are, in some sense, the
'same' maze. Is a twisted passage [with no choices] to a dead end
more or less difficult than a straight passage to the dead end?
Topologically, the mazes are identical, but you might well
intuitively argue that that straight-deadend one is _easier_
because you can more quickly "see" that it _IS_ a dead end. ["see"
in quotes because another aspect of this is what rules you impose
for traversing the maze. Doodling a simple maze on a piece of
paper [with a plan view of the whole maze] is a VERY different
matter from walking through one where you can only see
line-of-sight. And those are different still from the mathematical
approach to the maze, where you can only look at a single cell at a
time and must make a decision in which direction to exit the cell
before you can see what's beyond.
} Now let's look at a small portion of the first maze. Is this maze
} more difficult and if so, why?
}
} 8aaaaaaa8aaaa 8
} 8 8 8
} 8 aaaaa 8 8aaaaaaaa
} 8 8 8 C 8
} 8 8 aaaa8aaaa a 8aaaa
} 8 8 8 8 8 8
} 8 8aaaaaaaa 8 8 8 8aaa8
} 8 8 8 8 8 B 8
} 8 8 aaaa8 8aaa8 aaaaa 8aaaa
} 8 8 A 8 8
} 8 8aaaaaaaaaaaaaaaaaaa8aaaaaaaaaaa8
} Well, it's not difficult to start. There is only one path up to
} the location marked 'A'. At that location we have to choose
} between two paths. But, if we glance ahead in both directions we
} immediately see that one path is a dead end.
See, here is the type of place where being imprecise hurts you. In
what way can one "immediately see" that one path is a dead end: the
fact is that the 'view' from A is *identical* [but mirror reversed]
in both directions. [actually, in this particular case, you _can_
"immediately see", since it is trivial to *prove* that there _cannot_
be an exit from A by turning right, since you've completely circumnavigated
the possible places any such path could go, so no matter HOW it wiggles
and twists [and branches and loops], it _cannot_ get you out.
But consider this slight modification:
} 8aaaaaaa8aaaa 8
} 8 8 8
} 8 aaaaa 8 8aaaaaaaa
} 8 8 *** C 8
} 8 8 aaaa8aaaa a 8aaaa
} 8 8 8 8 8 8
} 8 8aaaaaaaa 8 8 8 8aaa8
} 8 8 8 8 8 B 8
} 8 8 aaaa8 8aaa8 aaaaa 8aaaa
} 8 8 A 8 8
} 8 8aaaaaaaaaaaaaaaaaaa8aaaaaaaaaaa8
} ^
I've removed one wall at "***'. Now, when you start and come to that
intersection, can you 'immediately see' that the two directions are part
of a loop? Obviously it will depend a LOT on what you mean both by
'immediately' and 'see'.
} ... If you continue
} through to the end of that maze you will notice that every time you
} have to choose between two paths you can always eliminate one by
} looking ahead and finding which one is a dead end.
Note that this is a topological property of the maze: if a maze is
treelike, then you can ALWAYS make that statement: every path is
either a dead end or leads to the finish.
} Now, although this slightly complicates the maze it does not make
} it very difficult. So, how can we complicate it further? What if
} we were to create a maze that would make it difficult to choose
} between the paths by pushing the dead ends farther away than in the
} examples we have seen so far. This would make it more difficult to
} choose the correct path on the first try. You would have to commit
} yourself to one or the other. And you could choose the wrong one,
} have to backtrack and take the other path.
But the truth is that you have to do that *anyway*. If you're going
to try to do some kind of analysis/synthesis, the distance to the
dead end has GOT to be irrelevant... since, if you think about it,
"commit yourself to one or the other. And you could... have to backtrack."
Is *exactly* what you do anyway, even in the simple case.
Your words:
} ... But, if we glance ahead in both directions we
} immediately see that one path is a dead end.
There's no real way to 'glance ahead' other than to commit, and if you
hit a dead end backtrack and try the other way, which is just what you
said would happen in the harder case... so upon more careful analysis,
I think that that does *NOT* affect the complexity.
} So, let's create a maze that offers, at the very beginning of the
} START path, a choice between 3 paths. Let's make those three paths
} as long as possible and connect only one of them with the FINISH.
} Here is such an example (the START is at the bottom):
}
} aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a
} 8 8 8 8 8 8 8 8
} 8 aaaaaaaaa 8 a 8 aaaaa 8 aaaaa aaaaa 8 8 a 8 8
} 8 8 8 8 8 8 8 8 8 8 8 8 8 8
} 8 8 a 8 8aaa8 8aaaa 8 8aaa8 aaaa8aaaaaaaa 8 8 8 8
} 8 8 8 8 8 8 8 8 8 8
} 8 8 8 8aaaaaaaaaaaaaaaaaaa8aaaa 8aaaaaaaaaaaa 8aaaaaaa8aaa8 8
} 8 8 8 8 8 8 8 8
} 8 8aaa8 a 8 aaaaaaaaaaaaa 8aaaaaaaaaaaa 8 a 8 aaaaaaaa8
} 8 8 8 8 8 8 8 8 8 8
} 8 aaaaa 8 8aaaaaaaa 8 8aaaaaaaaaaaa 8 8aaa8 8aaaaaaaa 8
} 8 8 8 8 8 8 8 8 8
} 8aaaaaaa8aaa8aaaaaaaa 8 8 a aaaaa 8 8aaaaaaaaaaaaaaaa 8 8
} 8 8 8 8 8 8 8 8 8 8
} 8 a aaaaaaaaaaaaaaaa8 8 8aaaa 8 8aaaaaaaaaaaa 8 8 8 8
} 8 8 8 8 8 8 8 8 8 8 8
} 8 8 8 aaaaaaaaaaaaaaaa8 8 aaaa8aaaaaaaa 8 8 8 aaaa8 8
} 8 8 8 8 8 8 8 8 8 8 8 8
} 8aaa8 8aaaa 8 a 8 aaaa8aaaa 8 aaaaaaaa8 8 8aaa8 aaaa8
} 8 8 8 8 8 8 8 8 8 8
} 8 a aaaaaaaa8 8 8aaaaaaaa 8 8aaaa 8 a 8aaaa 8aaaa 8
} 8 8 8 8 8 8 8 8
} 8 8aaaaaaaaaaaaaaa8aaaaaaaaaaaaaaa8aaaaaaa8aaaaaaa8aaaaaaa8aaaaaaaaaaa8
}
} So, did you select the correct path the first time? I certainly
} hope not! :-) You had one chance in three to do so if you started
} at the bottom. But, if you 'cheated' and started at the top
} (FINISH) you had an easy path all the way to the START. So, this
} is actually an example where it is easier to go in the reverse
} direction.
No, it isn't, if you're trying to be precise. *Regardless* of which way
you do the maze, forward or backward, you reach a point where you hit
an intersection that looks like:
} 8 8 8
} 8 8 8
} 8aaa8 8aaaa
} 8 X
} 8 a aaaaa
} 8 8
} 8 8aaaaaaaa
And you know nothing about *ANY* of the other three paths. Whether you
enter it from the top or enter it from the side, you still have one
chance in 3 of guessing right, regardless of which way you're doing
the maze. Again, we run into the unstated assumption about what
you are allowed to 'know' when you enter a cell and must make a decision.
Certainly from cell X, you cannot _see_ the exit [in the normal
sense of the term 'see', and while we agree that it is nearby, if the
maze were made infintessimally more twisted, say:
} 8 8 8
} 8 8 8
} 8aaa8 8aaaa
} 8 X
} 8 a aaaaa
} 8 8
} 8 8aaaaaaaa
| <---
|___________
Is it *now* still obvious that if you enter cell X from above that
a turn to the right is the way out?
} ... Hence, it is possible to create a maze in which one of
} the two directions is more difficult than the other.
We disagree on this point, until you go back and more carefully
address the twin matters: what are the rules for your traversal, and
what is your metric of difficulty.
} We can deduce from this that starting with the side that has the
} least amount of paths to choose from, makes the maze easier.
No we can't. The key point is that for all intents and purposes,
the local topology of the maze is *identical* whether you do it
backwards or forwards: as I highlighted above, you enter a cell
like 'X' above [especially in the second case where I wrapped
the entrance/exit around a corner] and it isn't at all clear that
that it is easier to pick the right way to exit the cell dependent
on which way you're traversing the maze.
} I hope you had some fun following the discussion and the examples.
} If you wish to create your own mazes use the following grid and
} replicate the bottom two lines as many times as you need to make a
} large rectangle of little squares.
}
} aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
} 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
} 8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8aaa8
Did you do this out of some kind of fancy graphics chars from the IBM
extended character set or something? All I got are lowercase-a's and
eights. Easy enough to figure out what you meant, but I've found that
underscores and vertical bars are a bit nicer looking if you stick to
vanilla ASCII:
_____________________________________________________________________
| | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
There is another whole area of maze difficulty you didn't even touch
on, which is loops and islands. Whether they make a maze a lot harder
or not is [yet again] dependent on what you decide the rules are for
traversing the maze. Fact is that a loop-free maze can be solved by
a finite state automaton[*], and so in a deeper sense they are all
about equally trivial. A general maze *cannot*.
[*] If you're not a fan of automata, you can rephrase this to say
"an algorithm that requires *only* a finite, fixed amount of
memory"
/Bernie\
--
Bernie Cosell ber...@fantasyfarm.com
Fantasy Farm Fibers, Pearisburg, VA (703) 921-2358
Original message headers
X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f996b,b912ea8e4126e777 X-Google-Attributes: gidf996b,public X-Google-ArrivalTime: 1994-03-04 12:24:08 PST Newsgroups: alt.ascii-art Path: gmd.de!xlink.net!news.dfn.de!news.belwue.de!zib-berlin.de!netmbx.de!Germany.EU.net!EU.net!howland.reston.ans.net!sol.ctr.columbia.edu!hamblin.math.byu.edu!news.byu.edu!news.kei.com!world!cosell From: ber...@fantasyfarm.com (Bernie Cosell) Subject: Re: DIS: The Maze Craze Message-ID: <E6Oqu*wb...@fantasyfarm.com> Sender: cos...@world.std.com (Bernie Cosell) Liines: 243 Organization: Fantasy Farm, Pearisburg, VA X-Newsreader: Arn V1.03a References: <Nve...@emr1.emr.ca> Date: Fri, 4 Mar 1994 20:24:08 GMT Lines: 243
Related ASCII art in the Gallery
Explore these categories from our collection of 11,000+ artworks:
Make your own ASCII art
Turn images, text or 3D into ASCII, or draw your own – right in your browser.
About this message.
This message was posted publicly to the newsgroup
alt.ascii-art
in 1994 and is mirrored here unchanged as part of the Historic Archives – only email addresses are masked.
The artwork and text belong to their original authors: if you copy a piece, keep the artist's initials or signature intact and credit them where you can.
Are you the author? Contact us to get your posts attributed, connected to your artist profile, or removed.
Report this message
Help us keep the archive clean and accurate. Reports are reviewed by a person – nothing is changed automatically.