Projects on Puzzles or Mazes

Date: 11/13/2002 at 23:39:35
From: Song Yee LeBaron
Subject:High school science projects

Hi,

I'm in the 10th grade and in my high school's science club, and I 
would like to do a mathematics project. I need a project soon, and I 
am having trouble finding a good project idea to use. My knowledge 
level: I'm taking calculus this year. I would like to do a project 
that involves applying mathematics to areas like puzzles or mazes. I 
would appreciate it VERY MUCH if you would send me some information on 
some project ideas!

Thanks so much,
Song Yee L.

Date: 11/15/2002 at 08:05:18
From: Doctor Ian
Subject: Re: High school science projects

Hi Song Yee, 

Do you have a favorite kind of puzzle? An analysis of why it works,
along with a method of generating other puzzles, might be interesting. 

For example, you're probably familiar with puzzles like this:

   Who Owns the Fish? (Einstein's Problem)
   http://mathforum.org/library/drmath/view/60971.html 

Would it be possible to come up with an _algorithm_ for making up
puzzles like this?  Or, if you're given one that someone has made up,
is there a way to tell, without working out the answer, whether the
clues in a puzzle are sufficient to come up with a solution?  Whether
the solution is unique?  

The point would be to come up with a 'theory of logic puzzles' that
would apply to _all_ puzzles of this sort. You could do a similar
thing with mazes - is there a way to tell, without actually finding a
solution to a maze, whether a solution exists, and is unique? 

Does this sound interesting? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 11/16/2002 at 14:19:29
From: Song Yee LeBaron
Subject: High school science projects

Hi Ian,

I like those ideas you mentioned, that's the kind of thing I was 
looking for. I have a question about how you said you could do a 
similar thing with mazes. What type of mazes are you talking about... 
or does it matter? Could you use the simple line mazes? And if so, 
where would be a good place to start, or to get information on this 
project idea?

Thanks again,
Song Yee L.

Date: 11/17/2002 at 09:25:17
From: Doctor Ian
Subject: Re: High school science projects

Hi Song Yee, 

A big part of doing the project would be defining what _you_ mean by a
maze, and finding a way to represent it that makes it accessible to
mathematical analysis.  

In the general sense, a 'maze' is anything that forces you to make a
sequence of decisions in order to get from some initial state to a
'goal state'.  In artificial intelligence, this is referred to as a
'search space', and a maze is just one particular way of visualizing a
search space.  

In fact, the choice of representation can make a huge difference. For
example, choose any maze, and let the start point be represented by
the root of a tree:

    Start

At the start point, you might be able to move in two possible 
directions, say east or north. Each decision would take you to a point 
that you could assign a unique label:

            #1
           /
          n
         /
    Start
         \
          e
           \
            #2

At point #2, you might be able to go east or south:

            #1
           /
          n
         /
    Start        #3
         \      /
          e    s  
           \  /   
            #2  
             \ 
              e
               \
                #4


And so on. Any time you find yourself returning to a place you've
already been, you can stop expanding from there, since you're
guaranteed to be exploring the consequences of being there in some
other part of the tree. 

When you get to the point where no further expansion is possible, you
have a tree that isomorphic to the maze - that is, the maze and the
tree are two different ways of looking at the same thing. But the new
representation allows you to answer some questions about the maze that
aren't obvious from the original representation, e.g., how many paths
(if any) lead to the goal state? What is the shortest path? What is
the longest (non-repeating) path, and so on?  Which kind of search -
'depth first' or 'breadth first' - would find a solution more quickly?

Similarly, you might transform the maze into a connected bidirectional
graph, and use graph theory to reason about it. 

Is this enough to get started? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/