Wanted: A maze you can't solve by keeping left
Peter Braham
A previous post requesting a maze design reminded me... I did read somewhere
that there are some mazes you can't solve by just keeping to the left wall, but
I can't remember the source and can't design such a one myself. Reference- or
best of all - example would be appreciated.
--
Peter Braham x471 email: pet...@tusc.com.au Ph: +61 (03) 840 4471
TUSC Computer Systems, 666 Doncaster Rd, Doncaster, Vic 3108, Australia
Bruno Wolff III
]
] A previous post requesting a maze design reminded me... I did read somewhere
] that there are some mazes you can't solve by just keeping to the left wall, but
] I can't remember the source and can't design such a one myself. Reference- or
] best of all - example would be appreciated.
Mazes with loops in them can't always be solved using the right hand rule.
However if the exit and entrance are both on the outer wall, you can use
the right hand rule to get from one to the other.
Jim Gillogly
Peter Braham <pet...@ephor.tusc.com.au> wrote:
>A previous post requesting a maze design reminded me... I did read somewhere
>that there are some mazes you can't solve by just keeping to the left wall, but
>I can't remember the source and can't design such a one myself. Reference- or
>best of all - example would be appreciated.
+----|Start|-----+
| |
| +----------+ |
| | | |
| | - |
| | Finish |
| | - |
| | | |
| +----------+ |
| |
+----------------+
--
Jim Gillogly
Highday, 10 Foreyule S.R. 1994, 23:51
spu...@pomona.edu
Hmm... a maze that can't be solved by keeping to the left wall. Well,
to begin with, this can't be the type of maze where you enter on one side and
exit on the other. These are all (I think) solvable in this way. It's just
pretty tedious. Oh, an additional condition is that they must be 2-dimensional
or else the method doesn't necessarily work.
The simplest is a circle with the entrance on the outside, the goal
in the middle, connected by a straight path and a loop going around the
outside. Choosing either wall as you go in will bring you back around to the
beginning. The easy way to compensate for such a situation is, when you enter
a intersection you've seen before by a path you haven't used before, pretend
it is a dead end, and turn around, thus changing walls. Of course, you have
to be able to recognize all the intersections in this method.
Sco4tt
Bernie Cosell
} A previous post requesting a maze design reminded me... I did read somewhere
} that there are some mazes you can't solve by just keeping to the left wall, but
} I can't remember the source and can't design such a one myself. Reference- or
} best of all - example would be appreciated.
Folks have already posted trivial examples of mazes that don't admit
of a "left hand rule". Let me just expand a bit on what's happening with
that: if you do the left [or right] hand rule, what you'll do is traverse
the *entirety* of the connected segment of wall from which you start.
This means that if you have a maze where the entrance and exit share a
wall [most common case: permeter of maze has just two openings, one is
the entrance and the other is the exit], you will *always* be able to
get though it [since the entrance and exit obviously are on the same
connected wall segment: just go around the outside to see].
But that is _all_ you can do with a handed-rule traversal. And so for
any maze that has where-you-are as NOT part of the same wall segment as the
exit will not be solvable with a handed-rule-traversal. Note that this
is not symmetric: the right-hand-wall might be connected to the exit, but
the left hand wall not, and so a right-hand-rule will get you out, but a
left-hand-rule will leave you stranded.
Here's one that I think is even MORE trivial than the examples you've
already seen of non-hand-rulable mazes [also demonstrates how 'which hand'
makes a difference]:
----- OUT ------
| |
| |
|
|
| |
| |
------ IN -------
Left hand rule puts you in a loop, while the right hand rule gets you out.
Another interesting exercise [interesting to me at least...:-)] is to
figure out an extension of the right-hand rule that'll work for 3-d
mazes. That is, imagine a maze bored out of a cube of wood by termites.
Can you come up with an right-hand-rule-like algorithm for traversing
the entirety of the connected segment to the wall on your right? [right
hand rule obviously won't make a lot of sense when you have to worry about
things like going up and down, and so you can instead consider if you can
design a finite-state-automaton that'll do the job].
/Bernie\
--
Bernie Cosell ber...@fantasyfarm.com
Fantasy Farm Fibers, Pearisburg, VA (703) 921-2358
--->>> Too many people; too few sheep <<<---
Seth Breidbart
Bernie Cosell <ber...@fantasyfarm.com> wrote:
>Another interesting exercise [interesting to me at least...:-)] is to
>figure out an extension of the right-hand rule that'll work for 3-d
>mazes. That is, imagine a maze bored out of a cube of wood by termites.
>Can you come up with an right-hand-rule-like algorithm for traversing
>the entirety of the connected segment to the wall on your right? [right
>hand rule obviously won't make a lot of sense when you have to worry about
>things like going up and down, and so you can instead consider if you can
>design a finite-state-automaton that'll do the job].
You can't design a finite-state automaton that'll do the job. In
fact, there's no finite-state pebble automaton (it has a finite number
of pebbles, which it can drop at intersections and will see and can
pick up later if and when it returns to that intersection). However,
the proof of the latter has eluded computer scientists (including me)
for several decades. (It's equivalent to proving NSPACE(log(n)) !=
DSPACE(log(n)).)
Seth
Raymond Weishaar
>From: Jim Gillogly <j...@acm.org>
>Subject: Re: Wanted: A maze you can't solve by keeping left
>Date: 30 Nov 1994 15:51:10 -0800
>In article <PETERB.94...@ephor.tusc.com.au>,
>Peter Braham <pet...@ephor.tusc.com.au> wrote:
>>A previous post requesting a maze design reminded me... I did read somewhere
>>that there are some mazes you can't solve by just keeping to the left wall, but
>>I can't remember the source and can't design such a one myself. Reference- or
>>best of all - example would be appreciated.
Keeping to the left wall doesn't guarantee getting to the finish, it only
guarantees that you get back where you started.
Ray W.
Bernie Cosell
Sorry but this is incorrect. Note that I did not say "solve the
maze": I said "traverse the entirety of the connected segment".
You cannot *solve* an arbitrary planar maze with a finite automaton
[although a finite automaton with exactly two pebbles will do the
job]. I don't know what happens when you extend to 3-space, but I
can try looking.. most of the research stuff I have on mazes is
mostly concerned with planar ones, so I don't know the state of the
art for *solving* [emphasis important!] 3-d mazes. On the other hand,
here on the farm I'm not likely to have access to any recent work so I
guess I won't find out about it either...:-)
BUT: for just traversing a connected segment... that's [relatively] easy.
Seth Breidbart
If you traverse the entire connected segment, then if the goal is in
that segment, you've reached to goal, so you've solved the maze.
There must be some difference of definition here.
Seth
Bruce Watson
although it is basically historical in nature.It is readily available in
Oz.
Bruce Watson
Jeff Adams
> >A previous post requesting a maze design reminded me... I did read somewhere
> >that there are some mazes you can't solve by just keeping to the left
wall, but
> >I can't remember the source and can't design such a one myself.
Reference- or
> >best of all - example would be appreciated.
Try any maze with a circuit separating START and FINISH. I'll
try my hand at a simple version below, but you get the idea.
_______________
| _________ |
| | | |
| | START | |
| | | |
| | | FINISH
| |____ ___| |
|_____________|
----------------------
Jeff Adams
ad...@math.uoregon.edu
James M. Devlin
a corner or on a wall. Compare a swimming pool with a ladder at the center;
if one keeps turning left around the walls, one never gets out. There book on
the mathematics of mazes; can't think of the titljust yet
but I'll get back to u.
Bernie Cosell
Indeed. The problem is your "if". Yes, **IF** the goal is
connected with the entrance then the maze is trivial [in _any_
number of dimensions: yes, you can extend the r.h.r not just to 3D
mazes but to any number of diimensions]. But that's not a general
maze, but rather a very restricted special case.
Now, as a practical matter, this does encompass one LARGE class of
mazes: 'transit' mazes... that is, mazes in which there is one
entrance from the outside and one exit to the outside and the
object is to enter the maze, wander through, and come out the other
side. Obviously, in such mazes the goal and the entrance are on a
connected segment and so the r.h.r [or its higher-dimensional form]
always works.
But it is not possible to solve a *general* maze with a
finite-state-automaton.
On that note, I've drawn a blank in doing some research
digging...does anyone know the 'pebbleness' of 3-D mazes? As I
mentioned, it has been know for about 30 years that you can solve
an arbitrary _planar_ maze with a FSA with two pebbles. I don't
know what the SotA is for cubic mazes... anyone have any pointers
[although it'd be hard for me to track down, nonetheless pointers to
articles/books would be fine..]
Thanks
bsm...@wci.com
: A previous post requesting a maze design reminded me... I did read somewhere
: that there are some mazes you can't solve by just keeping to the left wall, but
... if the maze starts at an interior point which is an 'island'...
--
Bob Smith
Wireless Connect, Inc
2177 Augusta Place, Santa Clara, CA 95051-1714
Voice: (408) 296-1546 FAX: (408) 296-1547