🚀 go-pugleaf

I was thinking about this in a research meeting today...

Suppose you have four dots, arranged in a square:

   A.  .B

   C.  .D

We want to connect the dots by straight line segments (no bends allowed).

How many ways can you draw a single continuous path of line segments from 
dot-to-dot that does not intersect itself?

In the example, we can draw:
  
  ABCD
  ABDC
  ACBD
  ACDB

but not ADCB or ADBC (since those paths intersect themselves).

Along with the symmetric paths that start at the other three points, 
there are a total of 16 possible paths.

QUESTIONS (ranging in difficulty):

1. How many circuits are there (instead of paths)?  Remember that a circuit
   is a path that has the same dot as both endpoints.  Example: ABDCA (but
   not ABCDA!).

2. Suppose you have 9 dots in a 3x3 square.  
   How many valid paths are there now?

   .A  .B  .C

   .D  .E  .F

   .G  .H  .I

   Note that a path is considered to have crossed itself if it goes through
   a dot that it previously passed through.  So, AG is not part of any
   legitimate path since it goes through D.

3. How many valid circuits are there in the 3x3 problem?

4. Supppose you have an NxN square. 
   How many valid paths are there through such a square?

5. How many valid circuits are there through an NxN square?

6. Suppose that we have blots instead of dots.  That is, our dots
   are now circles with non-zero circumference.  You are forbidden from
   passing through any part of a blot (unless you are going to that blot
   as part of the path).
   
   Clearly this makes the problem (very) difficult.  Is there an easy
   solution to any of the previous questions in general?

   Example:

   +--+A  oB
   |  |
   +--+
   oC  oD

   Now the segment BC will always intersect A, so it can't be part of any
   path.  In this case, the blots have different size (well, A does, anyhow).
   What if they all have the same (non-zero) size?
--

Matthew Merzbacher	ARPA:	matthew@CS.UCLA.EDU
Moo - Moo Moo  		UUCP:	...!{uunet|rutgers|ucbvax}!cs.ucla.edu!matthew
               		This time, *with* the oys