Original Usenet thread from alt.ascii-art, started 2 Mar 1994.
DIS: The Maze Craze
alt.ascii-art
· 7 messages · 2 Mar 1994 - 7 Mar 1994
Cool discussion! I have the following point to add in support of the
rationality of those who start at the finish:
If the maze-designer was assuming that a would-be solver would start at
a particular side, then they strove to make the maze difficult from this
direction. This doesn't *imply* that it will be easier from the other
direction, but I submit that this is more likely than not.
If the maze-designer designer kept an open mind about which side would
be START and which END, then they almost *certainly* chose START to be
what they thought was the harder entrance. Their judgement of relative
difficulty would be pretty reliable, I submit, given their exhaustive
knowledge of the maze.
-Matt Ryan, I dunno, I prefer "there's a cabin on a mountain..."
mbr...@midway.uchicago.edu Curious Of All Natures
================================== ====================================
If I'm dreaming, never let me wake. You'll never see the end of the road
If I'm awake, never let me sleep. When you're traveling with me.
-old chinese fellow -Crowded House
================================== ====================================
Normand Veilleux (nve...@emr1.emr.ca) 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? Basically this belief comes down to the psychology of the maze creator and that of the maze solver. Your logic in showing that a maze can be equally difficult from both ends or harder from either one or the other is infallible (if somewhat loosely reasoned), but the common belief is still often true because those who craft mazes tend to put in branches meant to confuse those who start at the beginning. Witness your attempt to show a maze offering 3 long choices: >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 Most maze creators tend to think along these lines: "How can I put in more tricks? Branch off at the start!" The very best mazes, though, do exactly what you did later on; they make many long branches from both ends so that there is no easy starting place. Of course, they often fail to put extra branches in the middle, so it can be useful in a tough maze to pick a point in the middle and try to connect it to both ends . . . Anyway, good discussion! (Not exactly sure that ascii-art is the place for it, though. Rec.puzzles??) -- _____ |\ /| G. Sumner Hayes | A man, a plan, a | O | gh2...@andrew.cmu.edu| canoe, pasta, hero's |/_\| rajahs, a coloratura, maps, snipe, percale, macaroni, a gag, a banana bag, a tan, a tag, a banana bag again (or a camel), a crepe, pins, spam, a rut, a Rolo, cash, a jar, sore hats, a peon, a canal, - Panama!
In article <Nve...@emr1.emr.ca> Nve...@emr1.emr.ca (Normand Veilleux) writes: >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? [Just A whole lot of ASCII-MAze stuff deleted] Normand.... Nice work... good theorizing.....Excellent use of paper. Even though I don't beleive this is the appropriate forum I'll throw in a little twist.... most people believe that working form the FINISH to the START is easier mostly because they start at the start and give up and work from the finish..... Ie. They in truth work from both ends... This is a very common mathmetical process. Given condition X prove Y... Normally Math Jocks will work in both directions and meet in the middle. You also get to see this Phenom. in that little word game, the one where you must change one word into another changing only one letter at a time, I think you'll discover most people work both ways in this game also. But only in mazes do people generally seem to forget that they have worked through the forward half of the maze before they start the back half. Just My 2c OB ART: (5-line monkey) ^ ^ ( . . ) ( d ) \ / (*) Ben
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
>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? what if it looks like... 8 8 8 8 8 8 8aaa8 8aaaa 8 X 8 aaaaa 8 8 aaaaaaaa you still have the three choices from the start, but going the other way you have a clear line of sight and IT IS immediately obvious which is the way out. ,d 88 ,adPPYba, MM88MMM ,adPPYba, 8b d8 ,adPPYba, ste...@maths.tcd.ie I8[ "" 88 a8P_____88 `8b d8'a8P_____88 ken...@unix1.tcd.ie `"Y8ba, 88 8PP""""""" `8b d8' 8PP""""""" aa `]8I 88, "8b, ,aa `8b,d8' "8b, ,aa `"Ybbd8"' "Y888 `"Ybbd8"' "8" `"Ybbd8"'
In article <2l9ti5$p3...@salmon.maths.tcd.ie>, Stephen Kennedy writes: } >} 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? } } what if it looks like... } } 8 8 8 } 8 8 8 } 8aaa8 8aaaa } 8 X } 8 aaaaa } 8 } 8 aaaaaaaa } } you still have the three choices from the start, } but going the other way you have a clear line of sight and } IT IS immediately obvious which is the way out. That's true: the *ONLY* places in the maze where there is any asymmetry is in those cells that can "see" the exit. The definition used for "see" will determine just which cells those are. If you mess with mazes mathematically, the usual defintion of 'see' is "the walls of the current [1x1] cell". so in your example: } 8 8 8 } 8 8 * 8 } 8aaa8 8aaaa } 8 Y X } 8 aaaaa } 8 Z W } 8 aaaaaaaa If we were using "proof like" definitions, then _only_ cell 'Z' would actually be able to 'see' the exit. If you're doing "geometrical line of sight", then you could even see the exit from '*' [and in fact, in the *actual original: } >} 8 8 8 } >} 8 8 * 8 } >} 8aaa8 8aaaa } >} 8 X } >} 8 a aaaaa } >} 8 8 } >} 8 8aaaaaaaa You might well *not* be able to see the exit from X [as asserted] but you probably *could* see it from cell '*', so you wouldn't even have to make a decision at 'X': as you traverse cell '*' you'd _just_ be able to see a slice of the exit ahead to your right, and you'd head straight there --- by the time you hit cell X you'd already know exactly where you were going, and so there'd be no decision to be made. I've never seen any actual theory on maze-difficulty using 'line of sight' adjacency. It would seem to make for some real odd anomalies, and so make any sorts of proofs difficult [e.g., just adding a 'tail' to the exit makes the maze more difficult line-of-sight ways [since cell 'X' now requires a choice, since you can't seen the exit any more]. but mathematically it would not have changed the _structure_ of the maze, and so generally not be accounted for. /Bernie\ -- Bernie Cosell ber...@fantasyfarm.com Fantasy Farm Fibers, Pearisburg, VA (703) 921-2358
Here's a sort of maze that cannot be run backwards easily. I drew a big one
on squared paper when I was young. If I can find the time I'll do it again
if this thread holds up.
You go from arrow to arrow, from the head of the arrow you choose
(if you have a choice) in the direction it points to the first tail
pointing in the same direction. This allows paths to cross freely
(which makes it a lot harder to see where you've been and where you
haven't) and by inserting extra arrows which are never used, you can
make the maze harder to trace in reverse.
Start--+-> +-+-+ --+--> +-+--+
| | | | | | | |
+-+- <-+-> | v v <-+ ---+ v |
| | | |
v +-> -+-> --+-> --+ <-+-> --+
| | | |
| ^ <-+-> ^ ^ | ^ +--+---
| | | | | | | | |
+-+-> -+---+ +-+-> +-+-+ --end
N.B. Arrow tails are only - or | ; + is a junction.
This is a tiny example and pretty easy. It has lots of dead ends or
arrows that point out of the maze altogether. However if you want to
create something hard in a small space, then maybe this is worth a try.
--
Richard Kirk Image Processing Group Crosfield Electronics Ltd. U.K.
ra...@crosfield.co.uk 0442-230000 x3361/3591 Hemel Hempstead, Herts, HP2 7RH
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 thread.
These messages were posted publicly to the newsgroup
alt.ascii-art
in 1994 and are 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 one of the authors? 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.