X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: f996b,b912ea8e4126e777
X-Google-Attributes: gidf996b,public
X-Google-ArrivalTime: 1994-03-06 13:38:26 PST
Newsgroups: alt.ascii-art
Path: 
 gmd.de!newsserver.jvnc.net!howland.reston.ans.net!news.intercon.com!panix!ddsw1!news.kei.com!world!cosell
From: bernie@fantasyfarm.com (Bernie Cosell)
Subject: Re: DIS: The Maze Craze
Message-ID: <iotru*Ib0@fantasyfarm.com>
Sender: cosell@world.std.com (Bernie Cosell)
Organization: Fantasy Farm, Pearisburg, VA
X-Newsreader: Arn V1.03a
References: <Nveilleu.186.762557880@emr1.emr.ca> <E6Oqu*wb0@fantasyfarm.com>>
 <2l9ti5$p3f@salmon.maths.tcd.ie>
Date: Sun, 6 Mar 1994 21:38:26 GMT
Lines: 75

In article <2l9ti5$p3f@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                               bernie@fantasyfarm.com
Fantasy Farm Fibers, Pearisburg, VA         (703) 921-2358